\documentclass[a4paper,12pt]{article}
\usepackage[utf8]{inputenc}
\usepackage[czech]{babel}
\usepackage{amsfonts}
\usepackage{graphicx}
\usepackage{enumerate}
\usepackage{amsmath}
\setlength{\parindent}{0.0in}
\setlength{\parskip}{0.1in}
\begin{document}

\section{Predslov}

Tento dokument obsahuje kompletné zápisky všetkého, čo sa objavilo na tabuli
behom prednášok predmetu Algebra 2, plus niekoľko málo vecí navyše, ktoré boli
len povedané. Kvôli rýchlemu tempu som ale nebol schopný zachystiť všetko, čo
bolo len povedané.

Do vzniku tohto dokumentu boli jediné dostupné materiály krátke stručné
poznámky k univerzálnej algebre na adrese\\
http://www.math.muni.cz/~polak/Algebra/Prednasky/univ-algebra-.ps.

Úspešnosť tohto predmetu bývala pred vznikom tohto textu... \emph{pestrá}, tak
dúfam, že sa táto štatistika zlepší.

Prajem veľa šťastia u skúšky.\\
Autor

P.S.: Pokiaľ objavíte matematickú chybu, ohláste mi ju prosím. Pokiaľ objavíte
pravopisnú chybu, nebude vám to nič platné, budem vám tvrdiť že to tak bolo na
tabuli :-).

\subsection{Doporučená literatura (jak zachyceno uchem):}

Burris: Universal Algebra (A course in...)\\
B. Davey: Introduction to Latices and Orders

\subsection{Poďakovanie}

Rád by som poďakoval doc. Liborovi Polákovi, že mi dal možnosť trochu skúšku
uľahčiť sebe i ostatným prípravou tohto textu, a tiež Honzovi Krihovi, bez
ktorého presviedčania by tento text nevznikol. V neposlednej rade ale chcem
hlavne poďakovať Andreji Čechovej za jej podporu v dobe tvorby tohto textu.

\section{22. 2. 2011}

$(R, +, \cdot)$ je těleso, pokud $(R, +)$ je grupa.

Příklad: $(R \setminus \{0\}, \cdot)$ je komutativní grupa.

algebraicky uzavřené = ireducibilní polynomy jsou právě lineární:\\
$f = a (x - c_1) ... (x - c_n) \leftarrow$ libovolný polynom

\includegraphics[height=50mm]{ilust/1.pdf}

Konečné těleso ($(\mathbb{Z}_n, +, \cdot)$ $n$ provčíslo) nemůže být
algebraické.

$(R, +, \cdot)$ konečné těleso\\
$R = \{a_1, ..., a_n)$\\
$(x - a_1)...(x - a_n) + 1$\\
$p$ prvočíslo, $f$ ireducibilní nad $\mathbb{Z}_p$, $n = \mathbf{st} f$\\
$(\mathbb{Z}_p[x] / (f), +, \cdot)$ je těleso o $p^n$ prvcích.

\subsection{Symetrické polynomy}

\subsubsection{Přepisování}

$A$ je konečná abeceda, $p q r \leftrightarrow p q^2 r$\\
$p, r \in A^*, q \in A^+, u,v \in A^*$\\
Cílem je rozhodnout, zda $u \sim v$, $\sim$ je ekvivalence na $\rightarrow$.

$a_nx^n + ... + a_1x + a_0$, $(R, +, \cdot)$ těleso, $a_n, ..., a_0 \in R$.\\
Chceme: $1, x, x^2, ...$ po 2 různé, $x = (0, 1, 0, 0, ...)$,
$a = (a, 0, 0, ...)$, $a \in R$\\
Zápis: $(a_0, a_1, a_2, ..., a_n, 0, 0, ...)$

Polynomy více proměnných:\\
$R[x,y] := (R[x])[y]$\\
$R[x_1, ..., x_n] := (...(R[x_1])[x_2]...)[x_n]$

$x = ((0, 1, 0, 0, ...), (0, ...), ...)$\\
$y = ((0, ...), (1, 0, ...), (0, ...), ...)$\\
$xy = ((0, ...), (0, 1, 0, ...), (0, ...), ...) = yx$

Formální řada: $(R, +, \cdot)$ semiring (např. okruh)\\
$A^* \rightarrow R$ libovolné zobrazení\\
Pro $R = \{0,1\}$ se jedná o zobecnění jazyků

$\varphi_{polynom}: \{u \in A^* | \varphi^{(u)} \neq 0\}$ konečné,
$a, b \in A, ab \neq ba$

Libovolné $f \in R[x_1, ..., x_n]$ je konečným součtem prvků tvaru\\
$ax_{i_1}^{k_1} ... x_{i_l}^{k_l}$, $i_1 < ... < i_l, l \in \mathbb{N}$

pro žádné členy $k_1, ..., k_l \in \mathbb{N}$\\
$ax_1^{m_1}x_2^{m_2} ... x_n^{m_n}, a \in R$ je člen stupně
$m_1 + ... + m_n$\\
$f = 2xy^2 + x^2y + xy^2$ má členy $3yx^2, x^2y$\\
$bx_1^{m'_1} ... x_n^{m'_n}$\\
$(m_1, ..., m_n) \neq (m'_1, ..., m'_n)$

$f$ je homogenní, jsou-li jeho členy stejného stupně.

$f$ je symetrický, je-li $\forall \pi \in \mathbb{S}_n$
$f(x_{\pi_1}, ..., x_{\pi_n}) = f$

$s_1 = x_1 + ... + x_n$\\
$s_i = \displaystyle\sum\limits_{j_1 < ... < j_i} x_{j_1} ... x_{j_i}$\\
$s_n = x_1 ... x_n$

\subsection{Hlavní věta o symetrických polynomech}

Definujeme $\leq$ na $\mathbb{N}_0 \times ... \times \mathbb{N}_0$:\\
$(k_1, ..., k_n) < (l_1, ..., l_n) \Leftrightarrow k_1 = l_1, ..., k_s = l_s,
k_{s + 1} < l_{s + 1}$\\
$\exists s \in \{0, ..., n - 1\}$\\
Jedná se o lexikografické uspořádání... zároveň je lineárním uspořádáním.

Vedoucí člen nenulového polynomu je člen, který je v tomto uspořádání přede
všemi ostatními.

\emph{\textbf{Lemma:} Vedoucí člen součinu dvou polynomů je součinem jejich
vedoucích členů těchto polynomů.}

\textbf{Důkaz:} Je-li $x_1^{k_1}...x_n^{k_n} > x_1^{k'_1}...x_n^{k'_n}$\\
$x_1^{l_1}...x_n^{l_n} > x_1^{l'_1}...x_n^{l'_n}$\\
pak $x_1^{k_1+l_1}...x_n^{k_n+l_n} > x_1^{k'_1+l'_1}...x_n^{k'_n+l'_n}$

\subsubsection{Newtonovy vztahy}

$f \in R[x], (R, +, \cdot)$ algrebraicky uzavřené těleso\\
$f = x^n + a_{n-1}x^{n-1} + ... + a_1x + a_0$\\
$f = (x - c_1) ... (x - c_n)$

\textbf{Důkaz:}\\
$f = x^n - (c_1 + ... + c_n)x^{n-1}\\
+ (...c_ic_j...)x^{n-2}\\
\vdots\\
(-1)^n c_1...x_n\\
= x^n - s_1(c_1, ..., c_n) x^{n-1} + ... + (-1)^{n-1} s_{n-1} (c_1, ..., c_n)x
+ (-1)^n s_n (c_1, ..., c_n)\\
s_k (c_1, ..., c_n) = (-1)^k s_{n-k}, k = 1, ..., n$

\emph{\textbf{Lemma:} Množství všech symetrických polynomů je podokruhem okruhu
$(R[x_1, ..., x_n], +, \cdot)$}

\textbf{Důkaz:} 0,1 symetrické\\
$f, g$ symetrické dá $-f, f + g, f \cdot g$ symetrické\\
$(-f)(x_{01}, ..., x_{0n} = -\underbrace{f(x_{01}, ..., x_{0n})}_{f}\\
(f + g)(x_{01}, ..., x_{0n}) = \underbrace{f(x_{01}, ..., x_{0n})}_{f} +
\underbrace{g(x_{01}, ..., x_{0n})}_{g}\\
(fg)(...)=...$

\emph{\textbf{Věta:} Hlavní věta o symetrických polynomech}\\
Nechť $f \in R[x_1, ..., x_n]$ symetrický, $(R, +, \cdot)$ komutativní, tak
$\exists ! g \in R[x_1, ..., x_n]$ tak, že $f = g (s_1, ..., s_n)$

\textbf{Příklad:} $x_1^2 + ... + x_m^2 = (x_1 + ... + x_n)^2-2(...x_ix_j...) =
s_1^2 - 2s_2\\
g = x_1^2 - 2x_2$

L z okruhů:

\includegraphics[height=50mm]{ilust/2.pdf}

$(R, +, \cdot)$ je komutativní okruh, $\alpha$ je homomorfismus. Pak $\exists!$
homomorfismus $R[x] \rightarrow S$ vlastní $x \mapsto t$ rozšiřující $\alpha$.

\textbf{Důkaz:} $a_nx^n + ... + a_1x + a_0 \mapsto \alpha(a_n)t^n + ... +
\alpha(a_1)t + \alpha(a_0)$. Jinak to není homomorfismus. Je to homomorfní
zobrazení.

\subsubsection{Reformulace hlavní věty}

\includegraphics[height=50mm]{ilust/3.pdf}

$\alpha: g(x_1, ..., x_n) \mapsto g(s_1, ..., s_n)$ je to homomorfismus podle
indukční věty\\
$d: R[x_1, ..., x_n] \subseteq R_{SYM}[x_1, ..., x_n]$ (je to podokruh)

Reformulace: $\alpha$ je prostý homomorfomismus na $R_{SYM}[x_1, ..., x_n]$.

Z věty: existence přejde na surjektivitu, jednoznačnost na injektivitu.

\textbf{Důkaz:} (konstruktivní)\\
$f_0 = f$ symetrický s vedoucím členem $ax_1^{k_1}...x_n^{k_n}, a \neq 0$\\
$as_1^{k_1-k_2}...s_{n-1}^{k_{n-1}-k_n}s_n^{k_n}$ má vedoucí člen\\
$a x_1^{k_1-k_2}(x_1x_2)^{k_2-k_3}...(x_1...x_n)^{k_n} =
ax_1^{k_1}x_2^{k_2}...x_n^{k_n}$\\
$g_1 = ax_1^{k_1-k_2}...x_n^{k_n}$, $f_1 = f_0 - \alpha(g_1) \rightarrow$
symetrický s vedoucím členem za vedoucím členem polynomu $f_0$.

$\exists g_2 \in R[x_1, ..., x_n]: f_2 = f_1 - \alpha(g_2)$ symetrický s
vedoucím členem za vedoucím členem polynomu $f_1$.

\emph{\textbf{Lemma:} $x_1^{k_1}...x_n^{k_n}$ vedoucí člen polynomu $f$ dá
$k_1 \geq ... \geq k_n$}

\textbf{Poznámka:} Kdyby $k_i < k_{i + 1}: \pi = (i, i+1)$

\vdots

$\exists g_p \in R[x_1, ..., x_n]: f_p = f_{p-1} - \alpha(g_p) = 0$\\
Vzhledem k lemmatu to skončí. Pak $f_0 = \alpha(g_1) + ... + \alpha(g_p) =
\alpha(\underbrace{g_1 + ... + g_p}_{g})$

Prostota $\alpha$:
$f = $ --- $ + $ polynom $ + ... + $ --- $ \stackrel{\alpha}{\mapsto} $ ---
$ + ... + $ ---. Polynomy napravo mají různé vedoucí členy.

\emph{\textbf{Lemma:} $\alpha: R \rightarrow S$ homomorfismus je prostý
$\Leftrightarrow (\alpha(x) = 0 \Rightarrow x = 0)$}

$\alpha(x^{k_1}, ..., x_n^{k_n}) =
\underbrace{s_1^{k_1}}_{x_1^{k_1+k_2}...x_{n-1}^{k_{n-1}-k_n}}...s_n^{k_n}
\mapsto k_1 - k_n...$

$n = 4$\\
$x_1^3 + x_2^3 + x_3^3 + x_3^3 + x_4^3$\\
Algoritmus: počítáme zvlášť homogenní části, vypíšeme všechny $k_1 \geq k_2
\geq k_3 \geq k_4$ aby to odpovídalo potenciálnímu vedoucímu členu za $x_1^3$,
$k_1 + ... + k_4 = 3$

$\begin{array}{cccccccc}
k_1 & k_2 & k_3 & k_4 & k_1 - k_2 & k_2 - k_3 & k_3 - k_4 & k_4\\
3 & 0 & 0 & 0 & 3 & 0 & 0 & 0\\
2 & 1 & 0 & 0 & 1 & 1 & 0 & 0\\
1 & 1 & 1 & 0 & 0 & 0 & 1 & 0
\end{array}$

$f = A \cdot s_1^3 + B \cdot s_1s_2 + C \cdot s_3, A, B, C \in R$\\
dosazovaním zjistíme $A, B, C$

$A = 1$ $(x_1 + x_2 + x_3 + x_4)^3\\
x_1 = x_2 = x_3 = 0, x_4 = 1\\
1 = A \cdot 1^3 + B \cdot 0 + C \cdot 0\\
B = ...\\
C = ...$\\
...atd jiné volby $x_1, ..., x_4$.

\section{1. 3. 2011}

\subsection{Uspořádané množiny a svazy}

Uspořádaná množina: $\mathcal{A} = (A, \leq)$, $A$ je množina, $\leq$ je relace
uspořádání na $A$, tj. reflexivní, tranzitivní a asymetrická relace.

\includegraphics[height=50mm]{ilust/4.pdf}

Pro $b > a$ kreslíme $b$ výže jak $a$. Spojíme dvojice. $a \prec b$ značí $a$
je pokryto $b$, resp. $b$ pokrývá $a$. $a \prec b \Leftrightarrow a < b,
\forall c (a \leq c < b \Rightarrow a = c)$

\includegraphics[height=50mm]{ilust/5.pdf}

$\mathcal{A} = (A, \leq)$ je uspořádaná množina, $X \subseteq A, a \in A$ je
\emph{horní závora} množiny $X$, je-li $\forall x \in X : x \leq a$.

$a \in A$ je \emph{suprémem} množiny $X$, je-li nejmenší horní závorou množiny
$X$.

$(A, \leq)$ je dualitou ke $(A, \geq)$.

$(A, \leq)$ je \emph{spojový polosvaz} $\exists$-li $\forall a, b \in A :
sup_\mathcal{A} \{a, b\}$. Duálně se jedná o \emph{průsekový polosvaz}.

$(A, \leq)$ je svaz je-li to spojový i průsekový polosvaz.

$(A, \leq)$ je úplný svaz má-li libovolná podmnožina $X \subseteq A$ suprémum i
infímum.

\emph{\textbf{Lemma:} Je-li $(A, \leq)$ uspořádaná množina v níž má libovolná
podmnožina $X \subseteq A$ infimum, pak $(A, \leq)$ je úplný svaz.}

\textbf{Pozn:} $(A, \leq)$ je úplný svaz, pokud libovolná podmnožina
$X \subseteq A, X \neq \emptyset$ má infímum a $\exists$ největší prvek.

\textbf{Důkaz lemmatu:} Nechť $X \subseteq A$, $Y$ množina všech horních závor
množiny $X$. $\exists a = inf Y$. Ukážeme, že $a = sup X$. Nechť $x \in X$,
chceme $a \geq x$. $x$ je dolní závora množiny $Y$, $a$ je největší dolní
závora $Y$. Teď víme, že $a$ je horní závora množiny $X$. Pro libovolní horní
závoru $b$ množiny $X$ je $a \leq b$.

$\mathcal{G} = (G, \cdot)$ je grupa. $S(G)$ je množina všech pologrup grupy
$G$. $(S(G), \subseteq)$ je (triviální) uspořádaná množina.

Průnik libovolného systému podgrup je podgrupa. Tedy infimem jsou průniky a je
to úplný svaz.

$H, K \in S(G)$, $H \cup K$ nemusí být podgrupa, suprémum ale existuje.

\includegraphics[height=50mm]{ilust/6.pdf}

Podprostory vektorového prostoru:\\
$sup \{H, K\} = H + K = \{h + k | h \in H, k \in K\}$.

Uzavřená množina metrického prostoru:

\includegraphics[height=50mm]{ilust/7.pdf}

$\varepsilon > 0$, $K(a, \varepsilon) = \{b \in M | d(a, b) < \varepsilon\}$
v metrickém prostoru

Otevřené množiny $\mapsto$ otevřené intervaly\\
$(a, b) | (a, \infty), \emptyset$ je otevřená\\
$a < b$

Speciální typy relací, např. relace ekvivalence na dané množině:\\
$\rho, \sigma \in Ekv A$\\
$(a, b) \in sup_{(Ekv A, \subseteq)}\{\rho, \sigma\} \Leftrightarrow
\exists n \in \mathbb{N}_0, c_0, ..., c_n$ takové, že\\
$a = c_0 \rho c_1 \sigma c_2 \rho ... c_n = b$

\emph{Algebraicky definovaný polosvaz:} $(A, \circ)$, kde $\circ$ je
asociativní, komutativní a idempotentní $(\forall a \in A : a \circ a = a)$.

\emph{Algebraicky definovaný svaz:} $(A, \wedge, \vee)$, kde $\wedge$ (průsek),
$\vee$ (spojení) jsou asociativní, komutativní, idempotentní a jsou vázany tzv.
absorbčními zákony: $\forall a, b \in A : a \wedge (a \vee b) = a,
a \vee (a \wedge b) = b$

\includegraphics[height=50mm]{ilust/8.pdf}

\begin{enumerate}[(i)]
\item
Pro spojový polosvaz $(A, \leq)$ je $(A, \vee)$ algebraicky definovaný
polosvaz, kde $a \vee b = sup_{(A, \leq)}\{a, b\}$.
\item
Pro algebraicky definovaný polosvaz $(A, \circ)$ je $(A, \leq)$ spojový
polosvaz, kde $a \leq b \Leftrightarrow a \circ b = b$ a
$sup_{(A, \leq)}\{a, b\} = a \circ b$ pro libovolné $a, b \in A$
\item
Uvedené přechody jsou vzájemně inverzní bijekce.
\end{enumerate}

\textbf{Důkaz (i):}
idempotence $\vee$: $sup \{a, a\} = a$\\
komutativita: $sup \{a, b\} = sup \{b, a\}$\\
asociativita: $(a \vee b) \vee c = a \vee (b \vee c)$ neboli
$sup \{sup \{a, b\}, c\} = \underbrace{sup \{a, sup \{b, c\}\}}_{a}$

$d$ je horní závora množiny $\{sup\{a, b\}, c\}$, ale máme
$d \geq a, sup\{b, c\}$, když $d \geq b, c$. Pak: $d \geq sup \{a, b\}$ a tedy
i $d \geq sup \{sup\{a, b\}, c\}$.

Nechť $e \geq sup \{a, b\}, c$, pak $e \geq a, b, c$, pak i
$e \geq sup \{b, c\}$, tedy i $e \geq d$.

\textbf{Důkaz (ii):}
reflexivita $\leq$ plyne z idempotence $\circ$.\\
tranzitivita: nechť $a \leq b \leq c$, pak $a \circ b = b, b \circ c = c$. Pak
i $a \circ c = a \circ (b \circ c) = (a \circ b) \circ c = b \circ c = c$\\
asymetrie $\leq$: $a \leq b, b \leq a$ dá $a \circ b = b, b \circ a = a$. Z
komutativity $\circ$ máme $a = b$. $sup_{(A, \leq)}\{a, b\} = a \circ b$
$a \leq a \circ b$ neboli $a \circ (a \circ b) \stackrel{?}{=} a \circ b$,
ale $a \circ (a \circ b) = (a \circ a) \circ b = a \circ b$.\\
$b \leq a \circ b$ podobně\\
$a, b \leq c$ dá $a \circ b \leq c$: neboli $a \circ c = c, b \circ c = c
\stackrel{?}{\Rightarrow} (a \circ b) \circ c = c$, ale $(a \circ b) \circ c =
a \circ (b \circ c) = a \circ c = c$

$(A, \leq) \mapsto (A, \vee)$ $a \vee b = sup_{(A, \leq)}\{a, b\}$\\
$(A, \vee) \mapsto (A, \preceq)$ $a \preceq b \Leftrightarrow a \vee b = b$\\
neboli $sup_{(A, \leq)}\{a, b\} = b$, neboli $a \leq b$.

$(A, \circ) \mapsto (A, \leq)$ $a \leq b \Leftrightarrow a \circ b = b$\\
$(A, \leq) \mapsto (A, \diamond)$ $a \diamond b = sup_{(A, \leq)}\{a, b\}$\\
$a \diamond b = sup_{(A, \leq)}\{a, b\} \stackrel{(ii)}{=} a \circ b$

\includegraphics[height=50mm]{ilust/9.pdf}

$a \preceq b \Leftrightarrow a \circ b = a$\\
$a \preceq b \Leftrightarrow a \circ b = b$

$a \wedge b = inf_{(A, \leq)}\{a, b\}$\\
$a \leq b$

\includegraphics[height=50mm]{ilust/10.pdf}

$a \wedge b = inf_{(L, \leq)}\{a, b\}\\
a \vee b = sup_{(L, \leq)}\{a, b\}$

Je potřeba ověřit absorbční zákony, tj. $a \wedge (a \vee b) = a$,
$a \vee (a \wedge b) = a$.

$inf \{a, sup \{a, b\}\} = a$\\
$a \leq b \Leftrightarrow a \wedge b = a$\\
$a \leq' b \Leftrightarrow a \vee b = b$

Zbývá $\leq = \leq'$ neboli $a \wedge b = a \Leftrightarrow a \vee b = b$\\
$\Rightarrow$: $b = b \vee (a \wedge b) = b \vee a$\\
$\Leftarrow$: $a = a \wedge (a \vee b) = a \wedge b$

Nechť $\mathcal{A} = (A, \leq), \mathcal{B} = (B, \leq)$ jsou uspořádané
množiny, pak $\alpha: A \rightarrow B$ se nazývá \emph{izotonní}, je-li
$\forall a, a' \in A : a \leq a'$ dá $\alpha(a) \leq \alpha(a')$.

$\alpha$ se nazývá \emph{vnoření}, pokud $\forall a,a' \in A : a \leq a'
\Leftrightarrow \alpha(a) \leq \alpha(a')$

$\alpha$ je \emph{izomorfismus} pokud je to bijektivní vnoření.

Vnoření je injektivní\\
$\alpha(a) = \alpha(a')$ dá $\alpha(a) \leq \alpha(a'), a \leq a'$,\\
$\alpha(a') \leq \alpha(a), a' \leq a$

\subsubsection{Věta o pevném bodě}
$(M, d)$ - metrický prostor, $\alpha : M \rightarrow M$ je kontrakce,
$\exists c < 1 : \forall a,b \in M : d(\alpha(a), \alpha(b)) \leq c \cdot
d(a,b)$

$M \subseteq \mathbb{R}^n$ konvexní kompaktní\\
$\alpha: M \rightarrow M$ spojitá. Pak $\exists a \in M : \alpha(a) = a$

\emph{\textbf{Věta o pevném bode}: $(L, \leq)$ úplný svaz,
$\alpha: L \rightarrow L$ izotonní, pak $\exists a \in L : \alpha(a) = a$}

\section{8. 3. 2011}

$a \leq b$ dá $\alpha(a) \leq \alpha(b)$

\subsection{Věta o pevném bodě}

$\mathcal{L} = (L, \leq)$ úplný svaz\\
$\alpha: L \rightarrow L$ izotonnní\\
Pak $\exists a \in L$ tak, že $\alpha(a) = a$

\textbf{Důkaz:}\\
$X = \{x \in L | \alpha(x) \geq x\}$\\
$a = sup X$\\
$\forall x \in X$ je $x \leq a, x \leq \alpha(x) \leq \alpha(a)$\\
$\alpha(a)$ je horní závora $X$, $a$ je nejmenší, tedy $a \leq \alpha(a)$, tj.
$a \in X$\\
$\alpha(a) \leq \alpha(\alpha(a))$, tj. $\alpha(a) \in K$, proto
$\alpha(a) \leq a$\\
Celkem: $\alpha(a) = a$

$(A, \circ), (B, \circ)$ polosvazy\\
$\alpha : A \rightarrow B$ ke homomorfismus vzhledem k $\circ$, je-li
$\alpha(a \circ a') = \alpha(a) \circ \alpha(a')$ (zejména to používáme pro
$\circ = \vee, \circ = \wedge$)

\emph{\textbf{Lemma:}}

\begin{enumerate}[(i)]
\item
$\mathcal{K} = (K, \vee), \mathcal{L} = (L, \vee)$ polosvazy, $\alpha$ je
$\vee-$homomorfismus dá $\alpha$ izotonní
\item
$\mathcal{K} = (L, \leq), \mathcal{L} = (L, \leq)$ svazy,
$\alpha : K \rightarrow L$.\\
Je ekvivalentní:
\begin{itemize}
\item
$\alpha$ je izomorfismus těchto uspořádaných množin
\item
$\alpha$ je izomorfismus svazů $(K, \wedge, \vee), (L, \wedge, \vee)$
\end{itemize}
\end{enumerate}

izomorfismus = bijektivní homorofmismus\\
homomorfismus svazů = homomorfismus vzhledem k $\wedge$ i $\vee$\\
izomorfismus svazů = bijektivní homomorfismus svazů

\textbf{Důkaz:}\\
(i) nechť $a \leq b$, tj. $a \vee b = b$\\
$\alpha(a) \vee \alpha(b) = \alpha(b)$\\
tj. $\alpha(a) \leq \alpha(b)$

(ii) $\Downarrow$ nechť $a, b \in K$, chci
$\alpha(a \wedge b) = \alpha(a) \wedge \alpha(b)$\\
(a podobně pro $\vee$)

Dokáži, že $\alpha(a \wedge b)$ je $inf\{\alpha(a), \alpha(b)\}$.\\
$\alpha(a \wedge b) \leq \alpha(a), \alpha(b)$ (je to dolní závora)\\
kdyby $\alpha(d) = c \leq \alpha(a), \alpha(b)$\\
kdyby $d \leq a, b$; $d \leq a \wedge b / \alpha$\\
$c = \alpha(d) \leq \alpha(a \wedge b)$

$\Uparrow$ $\alpha$ je bijekce, homomorfismus vzhledem k $\wedge$, tedy i
izotonní podle (ii). Zbývá $\alpha^{-1}$ izotonní.

Ukáži, že $\alpha^{-1}: L \rightarrow K$ je $\wedge$-homomorfismus.\\
$a, b \in L$, chci $\alpha^{-1}(a \wedge b) \stackrel{?}{=} \alpha^{-1}(a)
\wedge \alpha^{-1}(b)$ (*)\\
$\alpha(\alpha^{-1}(a) \wedge \alpha^{-1}(b)) = \alpha(\alpha^{-1}(a)) \wedge
\alpha(\alpha^{-1}(b)) = a \wedge b$\\
$a \wedge b / \alpha^{-1}$ dá (*)

\subsection{"Vaření čísel"}

\includegraphics[height=40mm]{ilust/11.pdf}

$\mathbb{N}_0: 0 = \emptyset$, následník: $a' = a' \cup \{a\}$\\
$\mathbb{Z}$: podobné konstrukci podílového tělesa\\
$\mathbb{Q}$: podílové těleso\\
$\mathbb{R}$: v analýze pomocí řezů, nebo zůplněním metrického prostoru,
v algebře zúplněním uspořádané množiny na úplný svaz.\\
$\not\exists sup\{x \in \mathbb{Q} | x^2 < 2\}$, v
$\mathbb{R}$ je to $= \sqrt{2}$\\
$\mathbb{C}$: $\mathbb{R}[x] / (x^2 + 1)$

\emph{\textbf{Lemma:} Libovolná uspořádaná množina jde vnořit do úplného
svazu.}

\textbf{Důkaz:}

$(A, \leq)$ dá $A \rightarrow 2^A; (2^A, \cap, \cup)$\\
$a \mapsto (a] = \{x \in A | x \leq a\}$\\
$a \leq b$ dá $\alpha(a) \subseteq \alpha(b)$

\includegraphics[height=50mm]{ilust/12.pdf}\\
Naopak též OK

\includegraphics[height=50mm]{ilust/13.pdf}

\subsection{Věta}

Libovolná uspořádaná množina $\mathcal{A} = (A, \leq)$ lze vnořit do úplného
svazu tak, aby byla zachována existující infima a supréma.

\textbf{Důkaz:}

\includegraphics[height=50mm]{ilust/14.pdf}

$J \subseteq A$ ideál, je-li $x < a \in J$ dá $x \in J$\\
$(a_i)_{i \in I}$ má suprémum $a$\\
všechna $a_i \in J$ dá $a \in J$\\
$I \neq 0$\\
$J(\mathcal{A}), \subseteq)$ je úplný svaz (je uzavřený na průniky)

$\alpha: A \rightarrow J(\mathcal{A})$\\
$a \mapsto (a] = \{x \in A | x \leq a\}$\\
\includegraphics[height=20mm]{ilust/15.pdf}\\
nechť $a_i \in A_i, i \in I \neq \emptyset$, $a$ nechť je
$sup_{\mathcal{A}}\{a_i | i \in I\}$\\
chceme $\alpha(a) = sup_{(J(\mathcal{A}), \subseteq)}\{\alpha(a_i) | i \in I\}$

$\forall i : a \geq a_i$, což dá $\alpha(a) \supseteq \alpha(a_i)$ - je to
horní závora.\\
Nechť $J$ je ideál, $\forall i \in I : J \supseteq \alpha(a_i)$.
(Chci $J \supseteq \alpha(a)$)\\

$J \ni a_i$, proto i $J \ni a$, $J \supseteq (a] = \alpha(a)$

Nechť $a_i \in A, i \in I \neq \emptyset,$
$a = inf_{\mathcal{A}}\{a_i | i \in I\}$\\
chci $\alpha(a) = inf_{(J(\mathcal{A}), \subseteq)}\{\alpha(a_i) | i \in I\}$

Máme $\forall i \in I : a \leq a_i$, proto $\alpha(a) \subseteq \alpha(a_i)$\\
$J$ je ideál v $\mathcal{A}$, $\forall i : J \subseteq \alpha(a_i)$\\
chci $J \subseteq \alpha(a)$\\
nechť $x \in J$, pak $\forall i : x \leq a_i$ a tedy $x \leq a$, tedy
$x \in \alpha(a)$

$\mathcal{A} = (A, \leq)$ lineárně uspořádaná množina. \emph{Řez} $(X, Y)$
splňující: $X, Y, \subseteq A; X, Y \neq \emptyset; X \cup Y = A$\\
$\forall x \in X, y \in Y$ je $x < y$.

$\mathcal{A}$
\includegraphics[height=25mm]{ilust/16.pdf}

typ řezu $(X, Y)$:
\includegraphics[height=25mm]{ilust/17.pdf}

ideály $\neq \emptyset, A$ odpovídají řezům typu 1, 2 a 4.\\
$J \leftrightarrow X$\\
řezy typu 2 a 3 jsou v přirozené bijekci\\
v $\mathbb{Q}$ nejsou řezy typu 1\\
\emph{\textbf{Def:} $\mathbb{R}$ jsou řezy typu 2 a 4.}

\subsection{Věta o nerovnosti ve svazech}

Nechť $\mathcal{L} = (L, \wedge, \vee)$ je svaz, $a, b, c \in L$. Pak

\begin{enumerate}[(i)]
\item
$a \wedge (b \vee c) \geq (a \wedge b) \vee (a \wedge c)$
\item
$a \vee (b \wedge c) \leq (a \vee b) \wedge (a \vee c)$
\item
$(a \wedge b) \vee (b \wedge c) \vee (c \wedge a) \leq (a \vee b) \wedge
(b \vee c) \wedge (c \vee a)$
\item
$a \leq c$ dá $a \vee (b \wedge c) \leq (a \vee b) \wedge c$
\end{enumerate}

(i) + (ii) - distributivní nerovnosti\\
(iii) - mediální nerovnost\\
(iv) - modulární nerovnost

\textbf{Důkaz:}

ad (i): stačí $a \wedge (b \vee c) \geq a \wedge b, a \wedge c$\\
stačí $a, b \vee c \geq a \wedge b, a \wedge c$

(iii): stačí $LS \leq a \vee b, b \vee c, c \vee a$\\
stačí $a \wedge b, b \wedge c, c \wedge a \leq a \vee b, b \vee c, c \vee a$

(iv): stačí $a \leq a \vee b, c; b \wedge c \leq a \vee b, c$

\emph{Distributivní a modulární svaz:}\\
Svaz $\mathcal{L} = (L, \wedge, \vee)$ je distributivní, platí-li\\
$\forall a, b, c \in L : a \wedge (b \vee c) = (a \wedge) \vee (a \wedge c)$.\\
Je modulární, platí-li $\forall a, b, c \in L : a \leq c$ dá
$a \vee (b \wedge c) = (a \vee b) \wedge c$

\includegraphics[height=50mm]{ilust/18.pdf}

\emph{\textbf{Lemma:} Libovolný distributivní svaz je modulární.}

\textbf{Důkaz:}

$(a \vee b) \wedge c \stackrel{distrib.}{=} (a \wedge c) \vee
(b \wedge c) = a \vee (b \wedge c)$

\includegraphics[height=50mm]{ilust/19.pdf}\\
není modulární: $a \vee (b \wedge c) = a, (a \vee b) \wedge c = c$

\includegraphics[height=50mm]{ilust/20.pdf}\\
není distributivní: $a \wedge (b \vee c) = a \wedge 1 = a$\\
$(a \wedge b) \vee (a \wedge c) = 0 \wedge 0 = 0$\\
je modulární - dokázáno později

\subsection{Věta}

Svaz je distributivní právě tehdy, když $\forall a, b, c :
a \vee (a \wedge c) = (a \vee b) \wedge (a \vee c)$

\textbf{Důkaz:}

$(a \vee b) \wedge (a \vee c) \stackrel{absorbce}{=}
((a \vee b) \wedge a) \vee ((a \vee b) \wedge c) =
a \vee ((a \vee b) \wedge c) =
a \vee ((a \wedge c) \vee (b \wedge c)) \stackrel{a \geq a \wedge c}{=}
a \vee (b \wedge c)$

\section{15. 3. 2011}

$a \vee (b \wedge c) = (a \vee b) \wedge (a \vee c)$\\
$a \wedge (b \vee c) = (a \wedge b) \vee (a \wedge c)$\\
ak jedno platí pro všechny $a, b, c$, platí aj druhé

\includegraphics[height=50mm]{ilust/21.pdf}\\
$a \leq c \Rightarrow a \vee (b \wedge c) \stackrel{\leq v\check{z}dy}{=}
(a \vee b) \wedge c$

distributivní $\Rightarrow$ modulární

\includegraphics[height=50mm]{ilust/22.pdf}\\
není modulární

\emph{\textbf{Lemma:} Svaz $\mathcal{L} = (L, \wedge, \vee)$ je modulární
$\Leftrightarrow \forall a, b, c \in L : a \vee (b \wedge (a \vee c)) =
(a \vee b) \wedge (a \vee c)$}

\emph{\quad\quad Pozn.: $\rightarrow$ od příští přednášky používat i text na stránkách}

\textbf{Důkaz:}
$\Rightarrow$: zřejmé\\
$\Leftarrow$: nechť $a \leq c$, pak ale $a \vee c = c$

\subsection{Věta}

Svaz $\mathcal{L} = (L, \wedge, \vee)$ je modulární
$\Leftrightarrow (\forall a, b, c \in L)(a \leq b, a \wedge c = b \wedge c,
a \vee c = b \vee c \Rightarrow a = b)$

\textbf{Důkaz:}

$\Leftarrow$: $a \stackrel{abs.}{=} a \vee (a \wedge c) = a \vee (b \wedge c)
\overset{a \leq b}{\underset{mod.}{=}} (a \vee c) \wedge b =
(b \vee c) \wedge b \stackrel{abs.}{=} b$

$\Rightarrow$: $x, y, z \in L, x \leq z$, chci $x \vee (y \wedge z)
\underset{\leq v\check{z}dy}{\geq} (x \vee y) \wedge z$

Položme $a = x \vee (y \wedge z), b = (x \vee y) \wedge z, c = y$

Stačí $a \wedge c = b \wedge c, a \vee c = b \vee c$

Ale $(\underset{\leq z}{x} \vee (\underset{\leq z}{y} \wedge z)) \wedge z \geq
(y \wedge z) \wedge y = y \wedge z$\\
$(x \vee y) \underset{\geq}{\wedge} z \wedge y = z \wedge y \leq z \wedge y$\\
$x \vee (y \wedge z) \vee y = x \vee y$\\
$((\underbrace{x \vee y}_{\geq x}) \wedge \underset{\geq x}{z}) \vee y
\leq (x \vee y) \vee y = x \vee y$\\
$\geq x \vee y$

\subsection{Věta}

$\mathcal{L} = (L, \wedge, \vee)$ svaz. $\mathcal{K}$ je jeho podsvaz, platí-li
$\mathcal{K} \subseteq \mathcal{L}, \forall a, b \in K :
a \wedge b, a \vee b \in K$. Pokrývání v podsvazu nemusí být pokrývání v
původním svazu.

\subsection{Věta}

$\mathcal{L} = (L, \wedge, \vee)$ je modulární $\Leftrightarrow$ nemá podsvaz
izomorfní s $\mathcal{N}_5$.

\textbf{Důkaz:}

$\Rightarrow$: $\mathcal{N}_5$ není modulární a proto ani $\mathcal{L}$ není
modulární

$\Leftarrow$: podle předchozí věty $\exists a, b, c \in L$ tak, že
$a < b, a \wedge c = b \wedge c, a \vee c = b \vee c$.

\includegraphics[height=50mm]{ilust/23.pdf}

Potřebuji: $|\{a, b, c, a \wedge c, a \vee c\}| = 5$

Případy:\\
$c = 0 / \vee a$ dá $1 = a$\\
$a = 0 / \vee c$ dá $1 = c$ (duální k $c = 0$)\\
$a = c / \vee b$ dá $a = 0$ - případ výše\\
+ 3 duální možnosti

\subsection{Věta}

Svaz $\mathcal{L} = (L, \wedge, \vee)$ je distributivní
$\Leftrightarrow (\forall a, b, c \in L)
(a \wedge b = a \wedge c, a \vee b = a \vee c \Rightarrow b = c)$

\emph{\textbf{Lemma:} $\mathcal{L} = (L, \wedge, \vee)$ je distributivní
$\Leftrightarrow \forall a, b, c \in L :
a \vee (b \wedge c) \geq (a \vee b) \wedge c$}

\textbf{Důkaz:}

$\Rightarrow$: $a \vee (b \wedge c) \stackrel{dist.}{=}
(a \vee b) \wedge (a \vee c) \geq (a \vee b) \wedge c$

$\Leftarrow: (a \vee b) \wedge (\underbrace{a \vee c}_{c}) \leq
a \vee (\underset{c}{b} \wedge (\underset{a}{a} \vee \underset{b}{c})) \leq
a \vee (a \vee (c \wedge b)) = a \vee (c \wedge b)$

\textbf{Důkaz věty:}

$\Rightarrow: b \stackrel{abs.}{=} b \vee (b \wedge a)\\
= b \vee (c \wedge a)\\
\stackrel{dist.}{=} (b \vee c) \wedge (b \vee a)\\
= (b \vee c) \wedge (a \vee c)\\
\stackrel{dist.}{=} (b \wedge a) \vee c\\
= (c \wedge a) \vee c \stackrel{abs.}{=} c$

$\Leftarrow: a, b, c \in L$. Ukážeme, že
$a \vee (b \wedge c) \geq (a \vee b) \wedge c$. \emph{(Lemma)}

Položme $x = (a \wedge
(\overbrace{\overbrace{b \vee c}^{})) \vee (\overbrace{b \wedge c}^{}}^{\geq})
\stackrel{mod.}{=} ((b \wedge c) \vee a) \wedge (b \vee c)$ (podle analogické
věty pro modální svazy)\\
$y = (b \wedge (c \vee a)) \vee (c \wedge a) = ...$\\
$z = (c \wedge (a \vee b)) \vee (a \wedge b) = ...$

$x \vee y = (\underbrace{\underbrace{a \wedge (b \vee c)}_{}) \vee
(\underbrace{\underbrace{b \wedge c}_{}) \vee (\underbrace{b \wedge
(c \vee a)}_{}}_{\leq}) \vee (\underbrace{c \wedge a}_{}}_{\geq}) =$\\
$= (a \wedge (\underbrace{\underbrace{b \vee c}_{})) \vee
(\underbrace{b \wedge (c \vee a)}_{}}_{\geq}) =$\\
$\stackrel{mod.}{=} ((\underbrace{\underbrace{b \wedge (c \vee a)}_{}) \vee
\underbrace{a}_{}}_{\geq}) \wedge (b \vee c) \stackrel{mod.}{=}$\\
$\stackrel{mod.}{=} (a \vee b) \wedge (c \vee a) \wedge (b \vee c)$\\
navíc jsou "duální"

podobně $y \vee z = z \vee x = (z \vee b) \wedge (b \vee c) \wedge (c \vee a)$

podobně $x \wedge y = y \wedge z = z \wedge x = (a \wedge b) \vee (b \wedge c)
\vee (c \wedge a)$

proto $x = y = z$

Závěr důkazu: $\underbrace{a \vee (b \wedge c)}_{\geq x} \stackrel{proto}{=}
\underbrace{(a \vee b) \wedge c)}_{\leq z}$\\
$x = z$

\subsection{věta}

Svaz $\mathcal{L} = (L, \wedge, \vee)$ je distributivní $\Leftrightarrow$ nemá
podsvaz izomorfní $\mathcal{M}_5$ nebo $\mathcal{N}_5$.

\textbf{Důkaz:} ...

\subsection{Reprezentace konečných distributivních svazů}

$\mathcal{L} = (L, \wedge, \vee)$ svaz, $a \in L$ je
\emph{spojově ireducibilní}, je-li $\forall b, c \in L (a = b \vee c$ dá
$a = b$ nebo $a = c$)

volný distributivní svaz se 3 generátory $\{a, b, c\}$\\
\includegraphics[height=50mm]{ilust/24.pdf}\\
$\Box$ - spojově ireducibilní

$J(\mathcal{L})$ - množina všech spojově ireducibilních, s eventuelní výjimkou
nejmenšího prvku.

$\mathcal{J}(\mathcal{L}) = (J(\mathcal{L}), \leq)$

$\mathcal{A} = (A, \leq)$ uspořádaná množina.

$H \subseteq A$ se nazývá \emph{dědičná}, je-li $\forall h \in H, a \leq h$ dá
$a \in H$.

Jestliže $H(\mathcal{A})$ množina všech dědičných množin uspořádané množiny
$\mathcal{A}$:\\
$\mathcal{H}(\mathcal{A}) = (H(\mathcal{A}), \subseteq)$

Nechť $\mathcal{L} = (L, \wedge, \vee)$ je konečný distributivní svaz, pak
$\mathcal{L} \cong \mathcal{H}(\mathcal{J}(\mathcal{L})) = $
$(H(J(\mathcal{L}), \leq), \subseteq)$

\includegraphics[height=50mm]{ilust/25.pdf}

$\mathcal{J}(\mathcal{L})$

\includegraphics[height=50mm]{ilust/26.pdf}

\textbf{Důkaz:}

$\alpha: L \rightarrow H(J(\mathcal{L}), \leq)$\\
$a \mapsto \{x \in J(\mathcal{L}) | x \leq a\}$ vede dobře

Každý prvek konečného svazu je suprémem vhodných prvků z $J(\mathcal{L})$

proto pro libovolný $a \in L$ je $a = sup_{\mathcal{L}}\alpha(a)$

Je-li $\alpha(a) = \alpha(b)$, je i $a = b$\\
máme prostotu

surjektivita: $X = \{x_1, ..., x_p\} \in H(\mathcal{J}(\mathcal{L}), \leq)$\\
$a = x_1 \vee ... \vee x_p$\\
$\alpha(a) = \{y_1, ..., y_q\} \supseteq \{x_1, ..., x_p\} = x$\\
$y_1 \vee ... \vee y_q = x_1 \vee ... \vee x_p$

$y_i = y_i \wedge (y_1 \vee ... \vee y_q) =
y_i \wedge (x_1 \vee ... \vee x_p) =$\\
$\stackrel{dist.}{=} (y_i \wedge x_1) \vee ... \vee (y_i \wedge x_p)$\\
$\exists j : y_i = y_i \wedge x_j$\\
t.j. $y_i \leq x_j$, proto $y_i \in X$

Tedy $\alpha(a) \subseteq X$\\
Celkem $\alpha(a) = X$

izotonní: zřejmě $a \leq b \Leftrightarrow \alpha(a) \subseteq \alpha(b)$\\
$a = sup \alpha(a)$

\begin{equation}
 \left.\begin{aligned}
        a = sup \alpha(a) \nonumber\\
        b = sup \alpha(b)
       \end{aligned}
 \right\}
 \leq
\end{equation}

\section{22. 3. 2011}

\subsection{Věta}

$\mathcal{L} = (L, \wedge, \vee)$ konečný distributivní svaz\\
$\mathcal{L} \cong H(\underbrace{J(\mathcal{L}, \leq)}_{A}, \subseteq)$

Omezený svaz: svaz s největším a nejmenším prvkem, označení $0, 1$.

$\mathcal{L} = (L, \wedge, \vee)$ omezený svaz, $a \in L$. $b \in L$ nazýváme
\emph{komplementem} prvku $a$, je-li $a \wedge b = 0, a \vee b = 1$.

\includegraphics[height=50mm]{ilust/27.pdf}
\includegraphics[height=50mm]{ilust/28.pdf}
\includegraphics[height=50mm]{ilust/29.pdf}

\subsection{Věta}

$\mathcal{L} = (L, \wedge, \vee)$ omezený distributivní:\\
\begin{enumerate}[(i)]
\item
libovolný prvek má nejvýše jeden komplement.
\item
má-li každý prvek komplement (komplementární svaz), má i v libovolné množině
$[a,b] = \{x \in L | a \leq x \leq b\}$ libovolný prvek komplement (je
relativně komplementární).
\end{enumerate}

\includegraphics[height=50mm]{ilust/30.pdf}

\textbf{Důkaz:}

(i) nechť $b, c$ jsou komplementy prvku $a$.
$b = b \wedge 1 = b \wedge (b \vee a) =
(b \wedge c) \vee (\underbrace{b \wedge a}_{0}) = b \wedge c
\Rightarrow b \leq c$\\
podobně $c \leq b$

(ii) $d$ nechť je komplementem $c$ v $\mathcal{L}$.\\
$e = (\underbrace{d \vee a}_{\geq a}) \wedge \underbrace{b}_{\geq a}, \leq b$,
$\stackrel{?}{\geq} a$\\
$c \vee ((d \vee a) \wedge b) \stackrel{?}{\leq b}$\\
$c = (\underbrace{c \vee d}_{1} \vee a) \wedge (\underbrace{c \vee b}_{b}) =
b$\\
$c \wedge (d \vee a) \wedge b \stackrel{c \leq b}{=} (d \vee a) \vee c
\stackrel{dist.}{=} (\underbrace{d \wedge c}_{0}) \vee
(\underbrace{a \wedge c}_{a}) = a$

$A$ množina, $X \subseteq 2^A$ je okruh množin na množině A, je-li
$X \neq \emptyset$ a je uzavřená na konečné průniky a sjednocení.
$(X, \cap, \cup)$ - je to distributivní svaz.

Pole množin na množině $A: X \neq \emptyset$ a je uzavřena na konečné
$\wedge, \vee$ a komplement.

$(X, \cap, \cup, ')$ je to booleaova algebra (přesněji:
$(X, \cap, \cup, \emptyset, A, ')$

\subsection{Booleova algebra}

Booleův svaz: omezený komplementární distributivní svaz.

Booleova algebra: $(B, \wedge, \vee, 0, 1, ')$, kde $(B, \wedge, \vee)$ je
distributivní svaz, $0 \wedge a = 0, 1 \wedge a = a$ pro libovolné $a$ a
$a \wedge a' = 0, a \vee a' = 1$.

\subsection{Věta}

Nechť $\mathcal{L} = (L, \wedge, \vee)$ je konečný svaz. Pak:
\begin{enumerate}[(i)]
\item
$\mathcal{L}$ je distributivní $\Leftrightarrow$ je izomorfní okruhu množin.
\item
$\mathcal{L}$ je booleův svaz $\Leftrightarrow$ je izomorfní poli podmnožin na
vhodné množině.
\end{enumerate}
\emph{Dokonce poli množin tvaru $(2^A, \cap, \cup)$.}

\textbf{Příklad}\\
$A$ je spočetná nekonečná množina. $X$ je množina všech jejich konečných a
kokonečných (komplementy konečných) podmnožin. Pak $(X, \cap, \cup)$ je
booleův svaz, ale není tvaru $(2^B, \cap, \cup)$.

$
|2^B| = \begin{cases}
\text{konečné pro }B\text{ konečné}\\
\text{kontinuum jinak}
\end{cases}
$

$|X| = \aleph_0$

\textbf{Důkaz:}\\
(i) $\Leftarrow$ víme\\
$\Rightarrow$ dědičné množiny na libovolné uspořádané množině tvoří okruh
množin a použije se věta (6.1).

$\mathcal{A} = (A, \leq)$

\includegraphics[height=50mm]{ilust/31.pdf}

(ii) $\Leftarrow$ víme\\
$\Rightarrow$

\includegraphics[height=50mm]{ilust/32.pdf}

Ukážeme, že $J(\mathcal{L}) = A$\\
$\supseteq$ OK, $\subseteq$:

\includegraphics[height=50mm]{ilust/33.pdf}

$\exists b: 0 < b < a$\\
$b$ má komplement $c$ v $[0, a]$. (svaz relativně komplementární).\\
t.j. $b \vee c = a, b \wedge c = 0$, pak $a = b \vee c; b, c \neq a$\\
spor s tím, že $a \in J(\mathcal{L})$.

Ve větě 6.1: $\mathcal{L} \cong (\underbrace{H, (A,
\underbrace{\leq}_{\text{triviální uspořádání}})}_{2^A}, \subseteq)$

...... (antiřetězec)

\subsection{Univerzální algebra}

$0 := \emptyset$, $n + 1 = n \cup \{n\}$, $n = \{0, 1, ..., n - 1\}$\\
$A^B =$ množina všech zobrazení množiny $B$ do množiny $A$
$(\subseteq B \times A)$\\
$A^n =$ množina všech uspořádaných n-tic prvků z $A$\\
$A^0 = \{\emptyset\}$\\
n-ární operace na $A$ je zobrazení $A^n \rightarrow A, n \geq 1$.\\
0-ární operace = výběr prvku

\emph{algebra:} $\mathcal{A} = (A, F)$, kde $A$ je množina a $F$ je množina
operací na $A$.

$F = \underbrace{F_0}_{\text{nulární}} \cup \underbrace{F_1}_{\text{unární}}
\cup \underbrace{F_2}_{\text{binární}} \cup ...$\\
arita: $F \rightarrow \mathbb{N}_0$

$\rho$ je kongruence algebry $\mathcal{A}$, je-li ekvivalencí na množine $A$ a
pro libovolné $n \in \mathbb{N}, f \in F_n, a_1, ..., a_n, b_1, ..., b_n \in A,
a_1 \rho b_1, ..., a_n \rho b_n$ dá $f(a_1, ..., a_n) \rho f(b_1, ..., b_n)$
(*)

\includegraphics[height=50mm]{ilust/34.pdf}

$\mathcal{A}/\rho = (A/\rho, \{f^{\mathcal{A}/\rho} | f \in F\})$\\
$f^{\mathcal{A}/\rho}(a_1\rho, ..., a_n\rho) = (f(a_1, ..., a_n))\rho$\\
$f \in F_n$\\
$[a]_\rho = \{b \in A | b \rho a\}$ píšeme $a\rho$\\
(*) je korektnost této definice

$\mathcal{G} = (G, \cdot)$ grupa

\includegraphics[height=50mm]{ilust/35.pdf}
$\mathcal{N}$ je normální podgrupa v $\mathcal{G}$

$\rho \mapsto 1\rho\\
\rho_N \mapsto N\\
a\rho_Nb \Leftrightarrow ab^{-1} \in N$

$\triangleleft$ - normální podgrupa\\
$\mathcal{N} \triangleleft \mathcal{G}$\\
chci $\rho_n \in Con\mathcal{G}$

reflexivita: $a \rho_N a$: t.j. $aa^{-1} \in N$ OK\\
symetrie: $a \rho_N b$, chci $b \rho_N a$\\
t.j. $ab^{-1} \in N$, chci $ba^{-1} \in N$\\
$Na(ab^{-1})^{-1} = ba^{-1}$\\
tranzitivita: $a \rho_N b \rho_N c$, chci $a \rho_N c$\\
t.j. $ab^{-1}, bc^{-1} \in N$, chci $ac^{-1} \in N$\\
OK, stačí vynásobit

zbývá $a \rho_N b, c \rho_N d$ dá $(ac) \rho_N (bd)$\\
t.j. $ab^{-1}, cd^{-1} \in N$, chci
$\underbrace{ac(bd)^{-1}}_{acd^{-1}b^{-1}} \in N$\\
$acd^{-1}b^{-1} = \underbrace{ab^{-1}}_{\in N}
\overbrace{b\underbrace{cd^{-1}}_{\in N}b^{-1}}^{\in N}$

$\mathcal{A} = (A, Q, \cdot, i, T)$ úplný deterministický konečný automat\\
$A = \{a_1, ..., a_n\}$ konečná abeceda\\
$Q$ konečná množina stavů\\
$\cdot: Q \times A \rightarrow Q$, rozšíříme do $Q \times A^k \rightarrow Q$\\
$i \in Q$ - iniciální stav\\
$T \subseteq Q$ - terminální stavy\\
$q \cdot 1 = q, q(ua) = (qu)a$

$p \mu q \Leftrightarrow \forall u \in A^* :
pu \in T \Leftrightarrow qu \in T$\\
$\mu$ - relace na $Q$

$\mathcal{L}_p(\mathcal{A}) = \{u \in A^* | pu \in T\}$\\
Zejména $\mathcal{L}(\mathcal{A}) = \mathcal{L}_i(\mathcal{A})$

minimalizace:
\begin{enumerate}
\item
odstraním nedosažitelné stavy
\item
dělím kongruencí $\mu$
\end{enumerate}

$f_i: Q \rightarrow Q, i = 1, ..., n$\\
$f_i(q) = q \cdot a_i$\\
$\mathcal{A} \mapsto
\overbrace{(Q, \underbrace{f_1, ..., f_n}_{F})}^{\overline{\mathcal{A}}}$

$\mu \in Con\overline{\mathcal{A}}$\\
$\mu \in Ekv Q$ OK\\
zbývá $p \mu q$ dá $\forall i : f_i(p) \mu f_i(q)$\\
$p \cdot a_i \mu q \cdot a_i$\\
$\forall v \in A^* (pa_iv \in T \Leftrightarrow qa_iv \in T)$

$R$ těleso, $(V, +)$ komutativní grupa, $\cdot : \overbrace{R}^{\text{skaláry}}
\times \overbrace{V}^{\text{vektory}} \rightarrow V$\\
$\alpha(Aa) = (\alpha B)a$\\
$1a = a$\\
$(\alpha + \beta)a = \alpha(a) + \beta(a)$\\
$\alpha(a + b) = \alpha(a) + \alpha(b)$\\
$\forall \alpha \in R$ definujeme $\lambda_\alpha : V \rightarrow V$\\
$a \mapsto \alpha a$

\subsection{Věta}

$(Con(A, f), \subseteq)$ je úplný svaz a je to úplný podsvaz svazu
$(Ekv A, \subseteq)$ - má největší prvek a je uzavřeno na průniky neprázdných
systémů.

\includegraphics[height=50mm]{ilust/36.pdf}

\section{29. 3. 2011}

$\mathcal{A} = (A, F)$, $ar: F \rightarrow \mathbb{N}_0$, $f \in F$\\
$\rho$ je \emph{congruence} algebry $F$, je-li $\rho$ ekvivalencí na $A$ a
$\forall f \in F$ n-ární, $a_1 \rho b_1, ..., a_n \rho b_n$ dá
$f(a_1, ..., a_n) \rho f(b_1, ..., b_n)$.

\includegraphics[height=50mm]{ilust/37.pdf}

\emph{\textbf{Lemma:} $(Con \mathcal{A}, \subseteq)$ je úplný svaz. Je to úplný
podsvaz svazu $(Ekv A, \subseteq)$.}

\textbf{Důkaz:}

\includegraphics[height=50mm]{ilust/38.pdf}

$(a, b) \in sup_{(Ekv A)}\{\rho_i | i \in I\}, I \neq \emptyset$\\
$
 \left.\begin{aligned}
        \Leftrightarrow a = c_0 \rho_{i_1} c_1 \rho_{i_2} c_2 ...
        \rho_{i_{n - 1}} c_n = b\\
        n \in \mathbb{N}_0, i_1, ..., i_{n - 1} \in I, c_1, ..., c_n \in A
       \end{aligned}
 \right\}
 \qquad \text{(*)}
$

\includegraphics[height=50mm]{ilust/39.pdf}
$(-\frac{1}{n}, \frac{1}{n}), n \in \mathbb{N}$,
$\underset{n \in \mathbb{N}}{\bigcap} (-\frac{1}{n}, \frac{1}{n}) = \{0\}$,
$\underset{n \in \mathbb{N}}{\bigwedge} (-\frac{1}{n}, \frac{1}{n}) =
\emptyset$

\textbf{Důkaz:}\\
$\{(a, b) | (*)\} =: X$\\
Dokáže se, že:
\begin{enumerate}
\item
$x \in Ekv A$
\item
$\forall i \in I : \rho_i \in A$
\item
$y \in Ekv A$, všechna $\rho_i \subseteq Y$ dá $X \subseteq Y$
\end{enumerate}

Nechť $I \neq \emptyset, \rho_i \in Con \mathcal{A}$, dokážeme
$\rho = sup_{(Ekv, \subseteq)} \{\rho_i | i \in I\} \in Con \mathcal{A}$\\
$f \in F$ n-ární, $(a_1, b_1), ..., (a_n, b_n) \in \rho$\\
chci $f(a_1, ..., a_n) \rho f(b_1, ..., b_n)$\\
$\exists c_{jk} \in A, i_{j,k} \in I$\\
$a_1 = c_{1, 0} \rho_{i_{1, 1}} c_{1, 1} \rho_{i_{1, 2}} ... c_{1, m_1 - 1} =
b_1$\\
$a_2 = c_{2, 0} \rho_{i_{2, 1}} c_{2, 1} \rho_{i_{2, 2}} ... c_{2, m_2 - 1} =
b_2$\\
$a_n = c_{n, 0} \rho_{i_{n, 1}} c_{n, 1} \rho_{i_{n, 2}} ... c_{n, m_n - 1} =
b_n$

$\rho, \tau \in Ekv, \exists n, ...$\\
$a = c_0 \rho c_1 \tau c_2 \rho c_3 \tau ... c_{2n - 1} \tau c_{2n} = b$

Vzhledem k reflexivitě můžeme předpokládat, že $m_1 = ... = m_n = m$\\
$f(\underbrace{a_1}_{= c_{1, 0}}, a_2, ..., a_n) \rho
f(c_{1, n - 1}, a_2, ..., a_n) \rho ... \rho
f(\underbrace{c_m}_{b_1}, a_2, ..., a_n)$\\
z 1. řádku:\\
$f(b_1, \underbrace{a_2}_{= c_{2, 0}}, a_3, ..., a_n) \rho
f(b_1, c..., a_3, ...) \rho ... \rho
f(b_1, b_2, a_3, ..., a_n)$

$\rho \in Con \mathcal{A}$\\
$Con(\mathcal{A}/\rho, \subseteq) \cong
(\{\tau \in Con \mathcal{A} | \tau \supseteq \rho\}, \subseteq)$

\includegraphics[height=50mm]{ilust/40.pdf}

typ: například $\tau = (2, 0, 1)$\\
$\tau = (n_\sigma)_{\sigma \in \Sigma}$\\
pro $\sigma \in \Sigma$ máme zvolený operační symbol $f_\sigma$, hovoříme o
\emph{jazyku}.\\
$(\cdot, 1, ()^{-1})$ - vhodné pro grupy

$\mathcal{A} = (A, (f_\sigma^\mathcal{A} |_{\sigma \in \Sigma})$\\
$f_\sigma \mapsto f_\sigma^\mathcal{A}$ n-ární operace

pro svazy $(2, 2)$, svaz $(\wedge, \vee)$\\
$\mathcal{L} = (L, \wedge^\mathcal{L}, \vee^\mathcal{L})$\\
Homomorfismus: $\mathcal{A} = (A, \cdot^\mathcal{A})$
$\mathcal{B} = (B, \cdot^\mathcal{B})$\\
$\forall a, a' \in A : f(a \cdot^\mathcal{A} a') = f(a) \cdot^\mathcal{B} f(b)$

\subsection{3.1 (lemma? věta?)}

$\rho \in Con \mathcal{A}$\\
$\rho^\#: A \rightarrow A/\rho$\\
$a \mapsto a\rho = [a]_\rho$\\
Je to surjektivní homomorfismus na $\mathcal{A}$ na $A/\rho$\\
surjektivita: OK\\
homomorfismus: $\sigma \in \Sigma, a_1, ..., a_{b_\sigma} \in A$\\
$\rho^\#(f_\sigma^\mathcal{A}(a_1, ..., a_{n_\sigma})) \stackrel{?}{=}
f_\sigma^{\mathcal{A}/\rho}(\overbrace{\rho^\#(a_1)}^{= a_1\rho}, ...,
\overbrace{\rho^\#(a_{n_\sigma})}^{= a_{n_\sigma}\rho})$\\
je to definice algebry $\mathcal{A}/\rho$.

\includegraphics[height=50mm]{ilust/41.pdf}

$b \mapsto b$ je prosté\\
$\sigma \in \Sigma, b_1, ..., b_{n_\sigma} \in B$\\
$\not\iota(f_\sigma^\mathcal{B}(b_1, ..., b_n)) \stackrel{?}{=}
f_\sigma^\mathcal{A}(\not\iota(b_1), ..., \not\iota(b_{n_\sigma}))$

Kongruence (typ(1))

\includegraphics[height=50mm]{ilust/42.pdf}

8 kongruencí: viz pozdější + se sjednocením $a$ s vhodnou třídou

\includegraphics[height=50mm]{ilust/43.pdf}\\
kongruence: $\Delta, A \times A, \{\{0, 2, 4\}, \{1, 3, 5\}\},
\{\{0, 3\}, \{1, 4\}, \{2, 5\}\}$

\includegraphics[height=50mm]{ilust/44.pdf}

3.1 (věta, nebo lemma?)\\
při hledání homomorfizmů stačí určit obraz nějaké množiny generátorů (stačí
$\{a\}$).

$ker \alpha = \{(a, a') \in A \times A | \alpha(a) = \alpha(a')\}$

\includegraphics[height=50mm]{ilust/45.pdf}

Ke 3.1 stačí, že $\beta: a\rho \mapsto \alpha(a)$ je homomorfismus.

Nechť $\sigma \in \Sigma, a_1, ..., a_{n_\sigma} \in A$\\
$\beta(f_\sigma^{\mathcal{A}/\rho}(a_1\rho, ..., a_{n_\sigma}\rho)
\stackrel{?}{=}
f_\sigma^\mathcal{B}(\beta(a_1\rho), ..., \beta(a_{n_\sigma}\rho))$\\
$LS = \beta((f_\sigma^\mathcal{A}(a_1, ..., a_{n_\sigma}))\rho)$ (definice
operace na faktor-algebře)\\
$PS = f_\sigma^\mathcal{B}(\alpha(a_1), ..., \alpha(a_{n_\sigma}))
\underset{\alpha \: je \: homomorfismus}{=}
\alpha(f^\mathcal{A}(a_1, ..., a_{n_\sigma}))$\\
$LS = PS$ - definice $\beta$

\textbf{Důkaz 3.1}\\
U předcházejícího lemmatu vezmeme $\rho = ker \alpha$\\
je to kongruence:
$\sigma \in \Sigma, a_1, ..., a_{n_\sigma}, b_1, ..., b_{n_\sigma} \in A$\\
$a_1 \rho b_1, ..., a_{n_\sigma} \rho b_{n_\sigma}$\\
chci $f_\sigma^\mathcal{A}(a_1, ..., a_{n_\sigma})\rho
f_\sigma^\mathcal{A}(b_1, ..., b_{n_\sigma})$\\
neboli $\alpha(a_1) = \alpha(b_1), ..., \alpha(a_{n_\sigma}) =
\alpha(b_{n_\sigma})$\\
chci $\alpha(f_\sigma^\mathcal{A}(a_1, ..., a_{n_\sigma})) =
\alpha (f_\sigma^\mathcal{A}(b_1, ..., b_{n_\sigma})$\\
ale $\alpha(f_\sigma^\mathcal{A}(a_1, ..., a_{n_\sigma})) =
f_\sigma^\mathcal{B}(\alpha(a_1), ..., \alpha(a_{n_\sigma})),
\alpha (f_\sigma^\mathcal{A}(b_1, ..., b_{n_\sigma}) =
(f_\sigma^\mathcal{B}(\alpha(b_1), ..., \alpha(b_{n_\sigma}))$

$\alpha(A)$ je podalgebra algebry $\beta$\\
$\sigma \in \Sigma, a_1, ..., a_{n_\sigma} \in A$\\
Pak $f_\sigma^\mathcal{A}(\alpha(a_1), ..., \alpha(a_{n_\sigma})) =
\alpha(f^\mathcal{B}(a_1, ..., a_n))$

\includegraphics[height=50mm]{ilust/46.pdf}

Podle lemmatu existuje a je to jediný homomorfismus
$\beta: \mathcal{A}/\rho \rightarrow \mathcal{B}$\\
$a\rho \mapsto ...\alpha(a)$\\
splňuje $\beta_{\rho^\#}$

uděláme $\beta$ surjektivní

zbývá $\beta'$ prosté\\
$\beta'(a\rho) = \beta'(b\rho)$\\
t.j. $\beta(a\rho) = \beta'(b\rho)$

definice $\beta:$\\
$\alpha(a) = \alpha(b)$\\
$a \rho b$

\section{5. 4. 2011}

$L \subseteq A^*, u, v \in A^*$\\
$u \sim_L u \Leftrightarrow \forall p, q \in A^* (puq \in L \Leftrightarrow pvq
\in L)$\\
$u \sim_L v$ dá $uw \sim_L vw, wu \sim_L wv$

původní definice kongruence:\\
$u \rho v, u' \rho v'$ dá $uu' \rho vv'$\\
stačí: $u \rho v$ dá $uw \rho vw, wu \rho wv$\\
$uu' \rho vu' \rho uv'$

Nechť $p, q \in A^*, puwq \in L$ proto $pvwq \in L$\\
dále podobně

$M_L = A^*/\sim_L, M_L$ - syntaktický monoid jazyka L

\subsection{Věta}

$M_L$ konečné $\Leftrightarrow$ $L$ regulární

$\mathcal{A} \stackrel{\alpha}{\rightarrow} \mathcal{B}\\
\mathcal{A} \stackrel{(ker \alpha)^\#}{\rightarrow>} \mathcal{A}/ker \alpha\\
\mathcal{A}/ker \alpha \underset{\beta\text{ izomorfismus}}{\rightarrow}
\alpha(\mathcal{A})\\
\alpha(\mathcal{A}) >\stackrel{\iota}{\rightarrow} \mathcal{B}$\\
$>\rightarrow$ surjektivita, $\rightarrow>$ injektivita

speciálně: $\alpha$ surjektivní dá $\mathcal{B} \cong \mathcal{A}/ker \alpha$

$A_i$ množina, $i \in I$\\
$\underset{i \in I}{\Pi} A_i = \{ f: I \rightarrow \underset{i \in I}{\bigcup}
A_i | \forall i \in I : f(i) \in A_i\}$ (součin, čast 4 z papírů)

pro $I \neq \emptyset$ konečné lze uvažovat $I = \{1, ..., n\}$ a píšeme
$A_1 \times ... \times A_n$

prvky zapisujeme ve tvaru $(a_i)_{i \in I}$ pro $I = \{1, ..., n\} :
(a_1, ..., a_n)$

$I = \emptyset : \underset{i \in \emptyset}{\Pi} A_i = \{\emptyset\}$

nechť $I \neq \emptyset$, některé $A_i = \emptyset$, pak
$\underset{i \in I}{\Pi} A_i = \emptyset$

Nechť dále $I \neq \emptyset$, všechna $A_i \neq \emptyset$\\
$\underset{i \in I}{\Pi} A_i \neq \emptyset$ je možná formulace
$\underbrace{(AC)}_{\text{axiom of choice - axiom výběru}}$

pro $I$ konečné je $\underset{i \in I}{\Pi} A_i \neq \emptyset$

\subsection{Zermelovo Lemma (ekvivalentní s AC)}

$\mathcal{A} = (A, \leq)$ uspořádaná množina, v níž má libovolný řetězec horní
závoru, pak $\forall a \in A : \exists b \in A : b$ je maximum v $A, a \leq b$.

$\tau = (n_\sigma)_{\sigma \in \Sigma}$ typ$_\mathcal{A}$,
($f_\sigma | \sigma \in \Sigma$ operační symboly)\\
$\mathcal{A}_i = (A_i, (f_\sigma^\mathcal{A} |_{\sigma \in \Sigma}),
i \in I)$\\
definujeme $\underset{i \in I}{\Pi} \mathcal{A}_i =
(\underset{i \in I}{\Pi} A_i,
(f_\sigma^{\underset{i \in I}{\Pi} \mathcal{A}_i}|
\sigma \in \Sigma)_{n = n_\sigma}$\\
kde $(f_\sigma^{\underset{i \in I}{\Pi} \mathcal{A}_i})
((a_i^1)_{i \in I}, ..., (a_i^n)_{i \in I}) \underset{\text{po složkách}}{=}
(f_\sigma^{\mathcal{A}_i} (a_i^1, ..., a_i^n))_{i \in I}$

\includegraphics[height=30mm]{ilust/47.pdf}

$\epsilon_i: \underset{j \in I}{\Pi} \mathcal{A}_j \rightarrow \mathcal{A}_i$\\
$(a_j)_{j \in I} \mapsto a_i$\\
je to homomorfismus, při $AC$ surjektivní

\subsection{Podpřímé součiny}

\includegraphics[height=50mm]{ilust/48.pdf}

Násobení uspořádaných množin:\\
$(a, b) \leq (c, d) \Leftrightarrow a \leq c, b \leq d$

Násobení svazů:\\
$(a, b) \leq (c, d) \Leftrightarrow
\underbrace{(a, b) \vee (c, d)}_{= (a \vee c, b \vee d)} = (c, d)\\
\Leftrightarrow a \vee c = c, b \vee d = d\\
\Leftrightarrow a \leq c, b \leq d$

\subsection{podřímé součiny, věta 4.1}

\includegraphics[height=50mm]{ilust/49.pdf}
příklad podle předešlé ilustrace

$(a_i)_{i \in I}, (b_i)_{i \in I}$\\
$((a_j)_{j \in I}, (b_j)_{j \in I}) \in
\underset{i \in I}{\bigcap} ker (\epsilon_i|B)$\\
Pak $\forall i \in I: ((a_j)_{j \in I}, (b_j)_{j \in I}) \in
ker (\epsilon_i|B)$\\
t.j.: $\forall i \in I: \epsilon_i((a_j)_{j \in I}) =
\epsilon_i((b_j)_{j \in I})$\\
t.j.: $\forall i \in I : a_i = b_i$

\includegraphics[height=50mm]{ilust/50.pdf}

Dále (doplněk věty)\\
$\mathcal{A}_i \cong \mathcal{B} / ker (\epsilon_i|B)$\\
(věta o homomorfismu)

tedy $B$ je izomorfní podpřímému součinu $(B / ker (\epsilon_i | B))_{i \in I}$

\subsection{věta 4.2}

$(\mathcal{B} / \rho_i)_{i \in I}, \underset{i \in I}{\bigcap}\rho_i = \Delta,
\mathcal{A} / \Delta_A \cong \mathcal{A}$\\
všechna $\rho_i \neq \Delta$, $\{a\} \leftrightarrow a$

\includegraphics[height=30mm]{ilust/51.pdf}

$(\mathbb{Z}_n, f)\\
f(i) = i + 1, i = 0, ..., n - 2\\
f(n - 1) = 0$

kongruence $\mathcal{A}$: právě $\rho_m$, kde $m|n$; zápis znamená, že
ztotožňuji ob $m$.

$\mathcal{A}/\rho_m = m$
\includegraphics[height=35mm]{ilust/52.pdf}

$\rho$ kongurence různá od $\Delta$\\
\includegraphics[height=40mm]{ilust/53.pdf}
kdyby $m \not| n$, $0 \rho m \neq 0$

dle definice je $\mathcal{A} = (\mathbb{Z}_{12}, f)$ podpřímo rozložitelná
$\mathcal{A}_n$ je podpřímý součin
$\underbrace{\mathcal{A}_n/\rho_4}_{\cong \mathcal{A}_4}$ a
$\underbrace{\mathcal{A}_n/\rho_6}_{\cong \mathcal{A}_6}$\\
\includegraphics[height=40mm]{ilust/54.pdf}

12-cyklus\\
\includegraphics[height=50mm]{ilust/55.pdf}

$\mathcal{A}$ je podpřímo nerozložitelná na součiny, když:\\
\includegraphics[height=50mm]{ilust/56.pdf}

$\mathcal{A}_n$ je podpřímo nerozložitelná $\Leftrightarrow$ $n = p^k, p$
prvočíslo. Kongruence $\rho$ pak vypadají:\\
\includegraphics[height=50mm]{ilust/57.pdf}

\subsection{důkaz věty 4.2}

\includegraphics[height=50mm]{ilust/58.pdf}\\
$b \mapsto (b\rho_j)_{j \in I} \mapsto b\rho_i$\\
$\alpha$ je prosté, neboť $\underset{j \in I}{\bigcap} \rho_j = \Delta$\\
$\alpha$ je homomorfismus:\\
$\sigma \in \Sigma, n = n_\sigma, b_1, ..., b_n \in B$\\
$\alpha(f_\sigma^\mathcal{B}(b_1, ..., b_n)) =
((f_\sigma^\mathcal{B} (b_1, ..., b_n))\rho_j)_{j \in I}$\\
$\stackrel{\text{definice operace na faktorové algebře}}{=}
(f_\sigma^{\mathcal{B}/\rho_j} (b_1\rho_j, ..., b_n\rho_j))_{j \in I}\\
\overset{\text{definice operace}}{\underset{\text{na součinu}}{=}}
f_\sigma^{\underset{j \in I}{\Pi} \mathcal{B}/\rho_j}
((b_1\rho_j)_{j \in I}, ..., (b_n\rho_j)_{j \in I}) =\\
= f_\sigma^{\underset{j \in I}{\Pi} \mathcal{B}/\rho_j}
(\alpha(b_1), ..., \alpha(b_n))$\\
Zbývá: $\forall i \in I : \epsilon_i\alpha : B \rightarrow B/\rho_i$
surjektivní\\
$b \mapsto b\rho_i$

\subsection{Věta 4.4}

\includegraphics[height=10mm]{ilust/59.pdf}
je jediný podpřímo nerozložitelný distributivní svaz

Důsledky $AC$:\\
$\mathcal{L}$ libovolný distributivní $\cong$ podsvazu
$\underset{i \in I}{\Pi}$ \includegraphics[height=3.3mm]{ilust/60.pdf}

$\underset{i \in I}{\Pi}$ \includegraphics[height=3.3mm]{ilust/60.pdf}
$\cong (2^I, \cap, \cup)$\\
$(a_i)_{i \in I} \mapsto \{i \in I | a_i = 1\}$\\
$\vee \qquad\qquad\qquad \cap$\\
$(b_i)_{i \in I}$

\includegraphics[height=30mm]{ilust/61.pdf}

\subsection{Důkaz věty 4.4}

$\mathcal{L} = (L, \wedge, \vee)$ distributivní svaz, $|L| \geq 3$\\
$\exists a, b_1, b_2 \in L : b_1 < a < b_2$\\
\includegraphics[height=15mm]{ilust/62.pdf}

$x \rho_1 y : \Leftrightarrow x \wedge a = y \wedge a$\\
$x \rho_2 y : \Leftrightarrow x \vee a = y \vee a$\\
$\rho_1 \in Con \mathcal{L} : \rho_1 \in Ekv L$ - jasné\\
$x \wedge a = y \wedge a \stackrel{?}{\Rightarrow} (x \wedge z) \wedge a =
(y \wedge z) \wedge a \stackrel{\stackrel{OK}{?}}{\Rightarrow}
(x \vee z) \wedge a = (y \vee z) \wedge a$\\
$(x \vee z) \wedge a = (x \wedge a) \vee (z \wedge a)
\underset{x \wedge a = a}{\stackrel{?}{=}}
(y \wedge a) \vee (a \wedge a)$

podobně $\rho_2 \in Con \mathcal{L}$\\
$\rho_1 \neq \Delta : b_2 \rho_1 a$\\
$\rho_2 \neq \Delta$

nechť $(x, y) \in \rho_1 \cap \rho_2$ - věta o distribuovaných svazech dá
$x = y$

\section{12. 4. 2011}

\subsection{(věta?) 4.1 (ii)}

\includegraphics[height=40mm]{ilust/63.pdf}\\
$\mathcal{L}$ libovolný distributivní\\
$(a_i)_{i \in I} \mapsto \{i \in I | a_i = 1\}$

Použito: Homomorfní obraz distributivního svazu je distributivní svaz

$\mathcal{L}$ libovolný booleův svaz\\
\includegraphics[height=50mm]{ilust/64.pdf}

$1 \mapsto (..., 0, ...)\\
\Downarrow\\
a \mapsto (\qquad 0 \qquad)\\
1 \mapsto (1)_{i \in I}$\\
máme podpřímý součin\\
$a \mapsto (a_i)_{i \in I}\\
b \mapsto (b_i)_{i \in I}$
\includegraphics[height=7mm]{ilust/65.pdf}\\
$\forall i \in I : \{a_i, b_i\} = \{0, 1\}$, tedy $i \in (\iota\alpha)(a)
\Leftrightarrow i \notin (\iota\alpha)(b)$\\
jinými slovami $(\iota\alpha)(b)$ je komplement $(\iota\alpha)(a)$

$\mathcal{A} = (A, (f_\sigma^\mathcal{A} |
\underbrace{_{\sigma \in \Sigma}}_{\text{zúžení }f\text{ na }\sigma}))$

$a, b \in A, a \neq b\\
\mathcal{Z} = (\{\rho \in Con \mathcal{A} | \neg(a \rho b)\}, \subseteq)$\\
nechť $\rho_i \in Con \mathcal{A}$ pro $i \in I$ tvoří řetězec\\
Platí $\underset{i \in I}{\bigcup} \rho_i \in Con \mathcal{A}$

Nechť $\sigma \in \Sigma, n = n_\sigma, a_1, ..., a_n, b_1, ..., b_n \in A$\\
$a_1 \rho b_1, ..., a_n \rho b_n$ dá $f_\sigma^\mathcal{A} (a_1, ..., a_n) \rho
f_\sigma^\mathcal{A} (b_1, ..., b_n)$\\
$\exists i_1, ..., i_n \in I : a_1 \rho_{i_1} b_1, ..., a_n \rho_{i_n} b_n$\\
Nechť $\rho_{i_0}$ je největší z $\rho_{i_1}, ..., \rho_{i_n}$\\
pak $a_1 \rho_{i_0} b_1, ..., a_n \rho_{i_0} b_n$\\
$f_\sigma^\mathcal{A} (a_1, ..., a_n) \underbrace{\rho_{i_0}}_{\subseteq \rho}
f_\sigma^\mathcal{A} (b_1, ..., b_n)$

Zbýva: sjednocení řetězce ekvivalencí je ekvivalence, tedy v uspořádané množině
$\mathcal{Z}$ $\exists$ nějaký maximální prvek, označme ho $\rho(a, b)$

$\underset{\underset{a \neq b}{a, b \in A}}{\bigcap} \rho (a, b) = \Delta$\\
(Pozn.: $\Delta$ = identita)\\
tedy $\mathcal{A} \cong$ podpřímému součinu systému
$\underbrace{\mathcal{A} / \rho(a, b)_{\underset{a \neq b}{a, b \in
A}}}_{\text{je to homomorfní obraz }\mathcal{A}}$

Zbývá pro $a, b \in A, a \neq b$ je $\mathcal{A} / \rho(a, b)$ podpřímo
nerozložitelné

\includegraphics[height=50mm]{ilust/66.pdf}

\includegraphics[height=30mm]{ilust/67.pdf}\\
$c \rho (a, b) \hat{\tau}, d \rho (a, b) \Leftrightarrow c \tau d$

\includegraphics[height=50mm]{ilust/68.pdf}\\
$\underset{i \in I}{\bigcap} \tau_i = \Delta$, libovolné $\tau_i \neq \Delta$\\
$\underset{i \in I}{\bigcap} \hat{\tau}_i = \rho (a, b),
\forall i : (a, b) \in \tilde{\tau}_i$,
libovolné $\tilde{\tau}_i \neq \rho(a, b)$

$A$ konečná abeceda, $K, L \subseteq A^*$\\
$u \sim_K v \Leftrightarrow \forall p, q \in A^* (puq \in K \Leftrightarrow
pvq \in K)$\\
$A^*/\sim_K$ syntaktický monoid jazyka $K$\\
$u \sim_K v \Leftrightarrow ... \in L \Leftrightarrow ... \in L$\\
$u \sim_{K \cup L} v \Leftrightarrow ...$\\
$u \sim_{K \cap L} v \Leftrightarrow ...$

$A^*/\sim_K\\
A^*/\sim_L\\
A^*/\sim_{K \cup L}$\\
$\uparrow$ jejich vztah = ?\\
$\sim_{K \cup L} \supseteq \sim_K \cap \sim_L$\\
$\sim_{K \cap L} \supseteq \sim_K \cap \sim_L$

$Con A^*$\\
\includegraphics[height=50mm]{ilust/69.pdf}
Je to homomorfní obraz $A^*/(\sim_K \cap \sim_L)$

$A^*/\sim_K \cap \sim_L$\\
\includegraphics[height=35mm]{ilust/70.pdf}

$A^*/\sim_{K \cup L}$ je homomorfní obraz podpřímého součinu $A^*/\sim_K$ a
$A^*/\sim_L$\\
$u \sim_{K \cup L} \mapsto (u \sim_K, u \sim_L)$\\
$A^* / (\sim_K \cap \sim_L) \stackrel{\text{prostý homomorfismus}}{\rightarrow}
A^* / \sim_K \times A^* / \sim_L$\\
$A^* / (\sim_K \cap \sim_L)
\stackrel{\text{surjektivní homomorfismus}}{\rightarrow}
A^* / \sim_{K \cup L}$

$(n_\sigma)_{\sigma \in \Sigma}, (f_\sigma)_{\sigma \in \Sigma}$\\
$(2, 1, 0) \qquad (+, ', 1)$\\
Dáno jazyk $\mathcal{L}$, množina $M$, definujeme $F_\mathcal{L}(M)$

\subsection{Termy}

$p \in F_\mathcal{L} (X_n)$ n-ární term\\
$p \mapsto p^{\mathcal{A}, n}$\\
$\mathcal{A} = (A, (f_\sigma^\mathcal{A})_{\sigma \in \Sigma})$\\
realizace $p$ na $\mathcal{A}$ - je to n-ární operace na množině $A$

\begin{enumerate}[(i)]
\item
$x_1, ..., x_n \in F_\mathcal{L} (n), x_i^{\mathcal{A}, n} (a_1, ..., a_n) =
a_i$
\item
$\sigma \in \Sigma, p_1, ..., p_{n_\sigma} \in F_\mathcal{L} (n) \qquad
(p_1^{\mathcal{A}, n}, ..., p_{n_\sigma}^{\mathcal{A}, n}$ již známe)\\
$(f_\sigma (p_1, ..., p_{n_\sigma}))^{\mathcal{A}, n} (a_1, ..., a_n) =
f_\sigma^\mathcal{A} (p_1^{\mathcal{A}, n} (a_1, ..., a_n), ...,
p_{n_\sigma}^{\mathcal{A}, n} (a_1, ..., a_n))$
\end{enumerate}

$\mathcal{A} \models p \simeq q : \Leftrightarrow p^{\mathcal{A}, n} =
q^{\mathcal{A}, n}\\
p, q \in F_\mathcal{L} (n)$

$(\sim, 1, 0)\\(+, ', 1)$\\
\includegraphics[height=50mm]{ilust/71.pdf}\\
$(x_2 + x_1') + ((1 + 1')' + x_1)$, \emph{ne}píšeme to ve stylu
$+(x_2, x_1), '(x_2))$

Jediný unární operační symbol $f$\\
n-ární termy: $x_1, ..., x_n$\\
$f(x_1), ..., f(x_n)$\\
$f(f(x_1)), ..., f(f(x_n))$\\
$f^{n + 1}(p) = f(f^n(p)), n \geq 1$\\
právě $f^p (x_q), p \in \mathbb{N}_0, q \in \{1, ..., n)$

$\mathcal{A} = (A, g), g: A \rightarrow A$

\emph{\textbf{Lemma:} $(f^p(x_q))^{\mathcal{A}, n} (a_1, ..., a_n) = g^p(a_q)$}

dosadíme $a$ za $x$, $g$ za $f$ (hodnoty za proměnné, operátor za operační
symbol)

\textbf{Důkaz:}
\begin{enumerate}[(i)]
\item
$LS = (x_q)^{\mathcal{A}, n} (a_1, ..., a_n) = a_q$\\
$PS = g^0(a_q) = a_q$
\item
$LS = (f(f^{p - 1}(x_q)))^{\mathcal{A}, n} (a_1, ..., a_n) =
f_\sigma^\mathcal{A}((f^{p - 1}(x_q))^{\mathcal{A}, n} (a_1, ..., a_n))
\stackrel{IP}{=}\\
g(g^{p - 1}(a_q)) = g^p(a_q), p \geq 1$
\end{enumerate}

jazyk unárních $f_1, ..., f_m$, n-ární termy\\
$f_{i_k}(...(f_{i_2}(f_{i_1}(x_q)))...), k \in \mathbb{N}_0, i_1, ..., i_k \in
\{1, ..., m\}, q \in \{1, ..., n\}$

$f(x_q), f \in \{f_1, ..., f_m\}^*, q \in \{1, ..., n\}$

$\mathcal{L}$ jazyk, $\Pi$ množina identit, $Mod \Pi$ - variety\\
cvičení: popis všech variet jazyka jediného operačního symbolu $f$ a to
unárního \emph{\{slovo nerozpoznáno\}}

$(A, g)$\\
\includegraphics[height=30mm]{ilust/72.pdf}\\
$A \models f^{n + d}(x) = f^n(x) \Leftrightarrow
\forall a \in A : g^{n + d}(a) = g^n(a)\\
n \in \mathbb{N}_0, d \mathbb{N}, n \geq 2, 12 | d$\\
ještě $\exists$ identity: $A \models f^n(x) = f^{n + d}(y), n, d \in
\mathbb{N}_0\\
\Leftrightarrow \forall a, b \in A : g^n(a) = g^{n + d}(b)$

Stačí: $f^n(x) = f^n(y)$\\
$g^3(a) = g^5(b) = g^4(a) = g(g(a)) = g^5(a)$

\section{19. 4. 2011}

$\mathcal{L}$ jazyk, $(n_\sigma)_{\sigma \in \Sigma},
(f_\sigma)_{\sigma \in \Sigma}\\
\mathcal{A} \models p = q : \Leftrightarrow p^{\mathcal{A}, n} =
q^{\mathcal{A}, n}$\\
$\Pi$ systém identit\\
$Mod \Pi = \{\mathcal{A} | \mathcal{A} \in \Pi\}$\\
$\Pi \underbrace{\models}_{\text{sémantický důsledek}}
\underbrace{\pi}_{p = q} : \Leftrightarrow \mathcal{A} :
(\mathcal{A} \models \Pi \Rightarrow \mathcal{A} \models \pi)$

binární $\cdot$, $\Pi = \{(xy)z = x(yz), x^2 = x\}$

$u, v \in X^*\\
u \sim v \Leftrightarrow v$ vzniklo z $u$\\
v konečném počtu kroků $pqr \rightarrow pq^2r, pq^2r \rightarrow pqr, p, r \in
X^*, q \in X^+$

Podle věty o úplnosti ekvacionální logiky
$(\Pi_B \models u = v) \Leftrightarrow u \sim v$

Ekvacionální klasifikace mononukleární algebry: vlastní variety jsou právě v
modeli

$v_{n/d} = Mod(f^{n + d}(x) = f^n(x)\}, n \in \mathbb{N}, d \in \mathbb{N}$\\
$w_m = Mod (f^m(x) = f^m(n)\}, m \in \mathbb{N}_0$

Variety daného jazyka tvoří vzhledek k inkluzi úplný svaz\\
\includegraphics[height=40mm]{ilust/73.pdf}

grupy $\mathcal{G} = Mod ((xy)z = x(yz), 1x = x1, x^{-1}x = 1, xx^{-1} = 1)$
jazyk\\
abelovské grupy $A\mathcal{G}_n = Mod (xy = yx, x^n = 1), n \in \mathbb{N}_0\\
(\cdot, 1, -1)\\
2, 0, 1$\\
\includegraphics[height=50mm]{ilust/74.pdf}

$Mod (x^n = 1, [x, y]^m = 1) \cap G$\\
$min [a, b] = a^{-1}b^{-1}ab$\\
2-nil potentní obdoba: $[x, [y, z]] = 1$

\subsection{Lemma 5.1 - důkaz:}

($f_\sigma(x_1, ..., x_n)$ - použití funkčního symbolu v termu)

Indukcí vzhledem ke složitosti $p$

\begin{enumerate}[(i)]
\item
$p = x_1\\
LS = \alpha (x_i^{\mathcal{A}, n} (a_1, ..., a_n)) = \alpha(a_i)\\
PS = x_i^{\mathcal{B}, n} (\alpha(a_1), ..., \alpha(a_n)) = \alpha(a_i)$
\item
(indukční krok)\\
$\sigma \in \Sigma$, nechť tvrzení platí pro $p_1, ..., p_{n_\sigma}$\\
dokážeme pro $f_\sigma(p_1, ..., p_{n_\sigma})$\\
Nechť $a_1, ..., a_n \in A$\\
$LS = \alpha((f_\sigma(p_1, ..., p_{n_\sigma}))^{\mathcal{A}, n}
(a_1, ..., a_n)) \stackrel{\text{definice realizace, krok 2}}{=}\\
f_\sigma^\mathcal{A}(p_1^{\mathcal{A}, n}
(a_1, ..., a_n), ..., p_{n_\sigma}^{\mathcal{A}, n} (a_1, ..., a_n))
\stackrel{\alpha\text{ je homomorfismus}}{=}\\
f_\sigma^\mathcal{B} (\alpha(p_1^{\mathcal{A}, n} (a_1, ..., a_n)), ...,
\alpha(p_{n_\sigma}^{\mathcal{A}, n} (a_1, ..., a_n)))$

$PS = (f_\sigma(p_1, ..., p_{n_\sigma}))^{\mathcal{B}, n}
(\alpha(a_1), ..., \alpha(a_n))\\
LS \stackrel{I.P.}{=} f_\sigma^\mathcal{B}(p_1^{\mathcal{B}, n}
(\alpha(a_1), ..., \alpha(a_n)), ...) = \\
(f_\sigma (p_1, ..., p_{n_\sigma}))^{\mathcal{B}, n}
(\alpha(a_1), ..., \alpha(a_n)) = PS$
\end{enumerate}

\subsection{věta 5.1}

$\alpha : \mathcal{A} \rightarrow \mathcal{B}$ surjektivní,
$\mathcal{A} \models p = q$ dá $\mathcal{B} \models p = q$

\textbf{Důkaz věty 5.1}\\
Nechť $p, q$ n-ární, $p^{\mathcal{A}, n} = q^{\mathcal{A}, n}$\\
$b_1, ..., b_n \in B, \exists a_1, ..., a_n \in A$ tak, že\\
$\alpha(a_1) = b_1, ..., \alpha(a_n) = b_n$\\
$p^{\mathcal{B}, n} (b_1, ..., b_n) = p^{\mathcal{B}, n}
(\alpha(a_1), ..., \alpha(a_n))$\\
(předešlá věta) $= \alpha(p^{\mathcal{A}, n} (a_1, ..., a_n))\\
= \alpha(q^{\mathcal{A}, n} (a_1, ..., a_n))\\
= q^{\mathcal{B}, n} (\alpha(a_1), ..., \alpha(a_n))\\
= q^{\mathcal{B}, n} (b_1, ..., b_n)$

Lehčí implikace Birkhoffovy věty\\
Variety jsou uzavřeny na operátory $\mathcal{H}, \mathcal{S}, \mathcal{P}$

$Mod \Pi$\\
příklad: grupy největší variety v jazyce binárního $\cdot$.\\
$(\mathbb{N}, +)$ je podalgebra $(\mathbb{Z}, +)$

\subsection{věta 5.4}

$\mathcal{A} = (A, (f_\sigma^\mathcal{A})_{\sigma \in \Sigma})$\\
\includegraphics[height=50mm]{ilust/75.pdf}

\begin{enumerate}[(i)]
\item
$M \subseteq X$
\item
$X$ je podalgebra
\item
$M \subseteq Y, Y$ podalgebra dá $X \subseteq Y$
\end{enumerate}

ad (i) $a \in M, x_1^{\mathcal{A}, 1} (a) = a, ...$\\
ad (iii) indukcí vzhledem ke složitosti $p$ - snadné\\
ad (ii) $\sigma \in \Sigma, n = n_\sigma, p_1^{\mathcal{A}, m_1}
(a_{11}, ..., a_{1m_1}), ..., p_n^{\mathcal{A}, m_n} (a_{n1}, ..., a_{nm_1}))
\in X$\\
$f_\sigma^\mathcal{A}$

svazy $\wedge^\mathcal{A} ((x_1 \vee x_2) \wedge x_4)^{\mathcal{A}, 4}
(a_{11}, ..., a_{14}) \qquad
(x_1 \vee x_8)^{\mathcal{A},3} (a_{21}, ..., a_{23})\\
{}^7(a_{11}, ..., a_{14}, a_{21}, ..., a_{23}) \qquad
(x_5 \vee x_3)^{\mathcal{A}, 7}$

(je tam vraj trik a vraj tomu netreba moc rozumieť) ${}_{\text{Polák}}$

pro $a_1, ..., a_n$ po 2 různá:\\
$p^{\mathcal{A}, n + 1} (a_1, ..., a_n, a_n)\\
q^{\mathcal{A}, n} (a_1, ..., a_n)\\
q := p <x_1, ..., x_n, x_n>$\\
($p<u_1, ..., u_n>$ - za $x_i$ dosaď $u_i$)

\subsection{Volné algebry}

Dáno: $\mathcal{V}, M$\\
Hledáme nejobecnější: $\mathcal{F}, \iota$

\includegraphics[height=50mm]{ilust/76.pdf}\\
$\mathcal{F} \in \mathcal{V}\\
<\iota(M)> = F\\
p^{\mathcal{F}, n} (\alpha(a_1), ... \alpha(a_n))$

unární operační symbol $f$\\
$\mathcal{V} = Mod(f^{5 + 2} (x) = f^5 (x)\}\\
M = \{a\}$

\includegraphics[height=50mm]{ilust/77.pdf}

$\mathcal{A}:$\\
\includegraphics[height=30mm]{ilust/78.pdf}

$\mathcal{V} = \{\mathcal{A}_n | n \in \mathbb{N}\}\\
\mathcal{A}_n :$\\
\includegraphics[height=40mm]{ilust/79.pdf}\\
žádná nemůže být nejobecnější

5 generátorů, distributivní svaz

\includegraphics[height=50mm]{ilust/80.pdf}

binární $\cdot$, $\mathcal{V}$ polosvazy,
$Mod (xy = yx, (xy)z = x(yz), x^2 = x)$

Volný polosvaz nad množinou $M$\\
$F$ = konečné podmnožiny množiny $M$\\
$\mathcal{F} = (F, \cup)$\\
$\iota: \underbrace{a}_{\in M} \mapsto \underbrace{\{a\}}_{\in F}$\\
$\underbrace{\{\{a\} | a \in M\}}_{\iota(M)}$\\
$K = \underbrace{\{a_1, ..., a_n\}}_{\{a_1\} \cup ... \cup \{a_n\}} \in F$

\includegraphics[height=50mm]{ilust/81.pdf}\\
$\{a\} \mapsto \alpha(a)\\
\{a_1, ..., a_n\} \stackrel{\beta}{\mapsto}
\alpha(a_1) \circ ... \circ \alpha(a_n) \stackrel{?}{=}
\alpha(b_1) \circ ... \circ \alpha(b_n)\\
\mathcal{A} = (A, \circ)$ je polosvaz\\
$\beta$ je korektně definováno

$\beta\iota = \alpha:\\
a \in M$ libovolné\\
$LS = \beta(\{a\}) = \alpha(a) = PS$

$\beta$ je homomorfismus:\\
$\beta(\{a_1, ..., a_n\} \cup \{b_1, ..., b_n\}) \stackrel{?}{=}
\beta(\{a_1, ..., a_n\}) \circ \beta(\{b_1, ..., b_n\})\\
LS = \beta(\{a_1, ..., a_n, b_1, ..., b_n\}) =
\alpha(a_1) \circ ... \circ \alpha(a_n) \circ \alpha(b_1) \circ ... \circ
\alpha(b_n)\\
PS = (\alpha(a_1) \circ ... \circ \alpha(a_n)) \circ (\alpha(b_1) \circ ...
\circ \alpha(b_n))$

\section{26. 4. 2011}

termíny zkoušky: týden 30. 5., pak po 14 dnech

volnost ve větě 6.1:
$M \stackrel{\iota}{\rightarrow} F\\
M \stackrel{\iota'}{\rightarrow} F'\\
F \stackrel{\exists \varphi\text{ izom }F \rightarrow F'}{\rightarrow} F'\\
\iota' = \varphi\iota$

\includegraphics[height=40mm]{ilust/82.pdf}

\includegraphics[height=30mm]{ilust/83.pdf}

$\overline{\iota'}\iota = \iota'\\
\overline{\iota}\iota' = \iota$

$O\mathcal \neq \mu\mathcal{A}\\
\iota' = \overline{\iota'} \overline{\iota} \iota'\\
\iota = \overline{\iota} \overline{\iota'} \iota$\\
ale $\iota' = \iota_{F'}\iota', \iota = 1_F \iota$\\
jednoznačnost faktorizace dá $\overline{\iota'}\overline{\iota} = 1_{F'}\\
\overline{\iota} \overline{\iota'} = 1_F$\\
($\uparrow$ jsou to vzájemně inverzní izomorfismy)

\subsection{Věta 6.3}

\includegraphics[height=50mm]{ilust/84.pdf}

$\nu(a) = (a \rho_i)_{i \in I}\\
\circ \iota = \nu\\
\mathcal{F} \in \mathcal{V}$

\includegraphics[height=30mm]{ilust/85.pdf}

nechť $\mathcal{A} \in \mathcal{V}_L$\\
$\alpha: M \rightarrow A$\\
$\exists$ homomorfismus
$\beta : \mathcal{F}_\mathcal{L} (M) \rightarrow \mathcal{A}$\\
$\beta\mu = \alpha$\\
věta o homomorfismu

\includegraphics[height=30mm]{ilust/86.pdf}

$\gamma : \underbrace{\mathcal{F}_\mathcal{L} (M)}_{\in \mathcal{V}} / \rho
\rightarrow \mathcal{A}_0$ izomorfismus\\
$\pi \cdot \gamma \cdot nat\rho = \beta$\\
$\exists i \in I : \rho = \rho_i$

"za $\beta$" vezmu $\pi\gamma\epsilon_i\overbrace{o}^{\text{omikron}}$\\
pak $\pi\gamma\epsilon_io\iota \stackrel{?}{=} \alpha$\\
ale $\pi\gamma\epsilon_io\iota = \pi\gamma\epsilon_i\nu\\
= \pi\gamma nat \rho_i \mu\\
= \beta\mu = \alpha$

(zejména variety (množiny všech modelů \emph{(ověřit)}) mají všechny volné
algebry)

\subsection{Věta 6.4 (budeme používat}

pologrupy s $\overbrace{LZ}^{\text{left zero}} = Mod(xy = x)$\\
pologrupy s termy: $x_{i_1} ... x_{i_k} \in X^+$\\
$i_1, ..., i_k \in \{1, ..., n\}$

\includegraphics[height=50mm]{ilust/87.pdf}

monoidové termy: prvky $X^+$

$x_{i_1} ... x_{i_k} = x_{j_1} ... x_{x_l} \in  Id LZ \Leftrightarrow
i_1 = j_1$

Volná Booleova algebra nad $X_n = \{x_1, ..., x_n\}$\\
kanonické tvary: $t = \underset{i = 1}{\overset{m}{\bigvee}}
x_1^{\epsilon_{i_1}} \wedge ... \wedge x_n^{\epsilon_{i_n}},
\epsilon_{i_j} \in \{-1, 1\}$\\
neopakují sa sčítanci\\
přesněji: podmnožiny množiny $\{-1, 1\}^n$, je jich $2^{2^n}$

$F_\mathcal{L} (M) / Id \mathcal{B}$\\
\includegraphics[height=30mm]{ilust/88.pdf}\\
operace:\\
$(\wedge, \vee, 0, 1, ')\\
(2, 2, 0, 0, 1)\\
n = 3\\
\{(-1, 1, -1), (1, 1, -1)\}$\\
příslušný term $(x' \wedge y \wedge z') \vee (x \wedge y \wedge z')$

libovolný term $u$ v $x_1 ... x_n$ upravíme na kánonický tvar tak, aby
příslušné úpravy byly identity: - s komplementem k proměnným\\
$(v \wedge w)' \rightarrow v' \vee w'\\
(v \vee w)' \rightarrow v' \wedge w'$

- u proměnné maximálně jeden komplement $u'' \rightarrow u$\\
- pomocí distributivity
$(\_ \wedge ... \wedge \_) \vee ... \vee (\_ \wedge ... \wedge \_)$\\
\hspace{10mm} $\_$ - proměnné a jejich komplementy\\
- přidám chybějící proměnné
$(x_{i_1}^{\epsilon_1} \wedge ... \wedge x_{i_p}^{\epsilon_p}) \rightarrow
(... \wedge x_i) \vee (... \wedge x_i')$\\
\hspace{10mm} chybí tam $x_i$ $\Rightarrow$ $= ... \wedge
(\underbrace{x_i \vee x_i'}_{1})$

$t, u$ kánonického tvaru, $t \neq u$\\
ukážeme, že \includegraphics[height=7mm]{ilust/65.pdf} $\not\models t = u$

$t$ obsahuje sčítanec
$\overset{1 ... 1}{x_1^{\epsilon_1} ... x_n^{\epsilon_n}}$ a $u$ nikoliv, nebo
naopak

$x_i \mapsto 1$ pro $\epsilon_i = 1$\\
$0$ pro $\epsilon_i = -1$\\
pak $t \mapsto 1, u \mapsto 0$

Volný distributivní svaz nad $X_n = \{x_1, ..., x_n\}$\\
kánonické tvary $t = \underbrace{\bigvee_{i = 1}^{m}
\underbrace{x_1 \wedge ... \wedge x_{ip_i}}_{
\text{po 2 různé, nezáleží na pořadí}}}_{\text{nezáleží na pořadí}},
p_i, m \in \mathbb{N}, x_{ij} \in \{x_1, ..., x_n\}$

$\{x_{i1}, ..., x_{ip_i}\}, \{x_{j1}, ..., x_{jp_j}\}$, nesrovnatelné pro
$i \neq j$, kdyby $\subseteq$, pravý vynechám

kánonické tvary konečné\\
neprázdné po 2 nesrovnatelné konečné neprázdné podmnožiny množiny $X$

$u$ libovolné $\qquad \rightarrow ... \rightarrow$ kánonický

$t, u$ dva různé kánonické tvary\\
ukážeme, že \includegraphics[height=7mm]{ilust/65.pdf} $\not\models t = u$\\
$t$ obsahuje $x_{i_1} \wedge ... \wedge x_{i_p}\\
x_{i_1}, ..., x_{i_p} \mapsto 1$\\
ostatní $\mapsto 0$

$\_ \vee
\underset{1}{\underset{x_{i_1} \wedge ... \wedge x_{i_p}}{\overset{t}{\_}}}
\vee \_ \vee \_ \stackrel{?}{=} \_ \vee
\underset{x_{j_1} \wedge ... \wedge x_{j_q}}{\overset{u}{\_}} \vee \_ \vee \_$

$\{i_1, ..., i_p\} \supseteq \{j_1, ..., j_q\}$

není tam takové $\{j_1, ..., j_q\}$ - OK\\
jinak hledáv v $t$\\
$x_{k_1} \wedge ... \wedge x_{k_r}$\\
není takové vlastnosti\\
$\{k_1, ..., k_r\} \subseteq \{j_1, ..., j_q\}$ - OK\\
$\{i_1, ..., i_p\} \supseteq \{j_1, ..., j_q\}$\\
$\{i_1, ..., i_p\} \supseteq \{k_1, ..., k_r\} \subseteq \{j_1, ..., j_q\}$

\includegraphics[height=7mm]{ilust/65.pdf} $\models t = u$ dá $t = u$

\subsection{Přepisovací systémy}

Dané $\rightarrow \subseteq M \times M$\\
chceme popsat ekvivalenci $\sim$ generovanou relací $\rightarrow$

\includegraphics[height=20mm]{ilust/89.pdf}

lokální konfluence:\\
\includegraphics[height=50mm]{ilust/90.pdf}

konfluence:\\
\includegraphics[height=50mm]{ilust/91.pdf}

\subsection{Věta:}

$\underbrace{N}_{\text{noetherovská}},
\overbrace{LC}^{\text{lokálně konfluentní}}$ dá $\rightarrow
\underbrace{C}_{\text{konfluentní}}$

\emph{\textbf{Lemma 9.1:}}

\textbf{Důkaz:}

$\rightarrow \subseteq T \times T$, $C,N$
\begin{enumerate}[(i)]
\item
$\stackrel{\rightarrow}{t} = u$ - kánonický tvar\\
$t \rightarrow ... \rightarrow u \not\rightarrow$\\
$t \rightarrow ... \rightarrow w \not\rightarrow$\\
z důvodu $C$ se spojí do jednoho prvku
\item
$t \sim u \Leftrightarrow \stackrel{\rightarrow}{t} =
\stackrel{\rightarrow}{u}$\\
$\Rightarrow:$\\
\includegraphics[height=40mm]{ilust/92.pdf}\\
\includegraphics[height=30mm]{ilust/93.pdf}

$\Leftarrow:$\\
\includegraphics[height=40mm]{ilust/94.pdf}

Hlavní problém: Dána ekvivalence $\sim$ na $M$\\
(zatím neefektivně) hledáme $N, C \rightarrow$ na $M$ tak, aby $\sim$ byla
příslušnou ekvivalencí
\end{enumerate}

\section{3. 5. 2011}

1., 15., 29. 6. - pravděpodobné termíny

\subsection{Noetherovská indukce}

$(A, \leq)$ uspořádaná množina v níž neexistuje $a_1 > a_2 > ...$\\
$\mathcal{P}$ vlastnost prvků z $A$\\
$\mathcal{P}(a): a$ má vlastnost $\mathcal{P}$\\
$\neg\mathcal{P}(a): a$ nemá vlastnost $\mathcal{P}$\\
$((\mathbb{N}, \leq) \qquad \mathcal{P}(n): 1 + 2 + ... + n \stackrel{?}{=}
\frac{n(n + 1)}{2})$

\subsection{Věta o indukci}

$(\forall a \in A) ((\forall b \in A, b < a \Rightarrow \mathcal{P}(b))
\Rightarrow \mathcal{P}(a))$ implikuje $\forall a \in A : \mathcal{P}(a)$

\textbf{Důkaz:}\\
Nechť platí $(\forall a \in A) ((\forall b \in A, b < a \Rightarrow
\mathcal{P}(b)) \Rightarrow \mathcal{P}(a))$ a nechť $\neg\mathcal{P}(a_1)$.
Proto $\exists a_2 < a_1 : \neg\mathcal{P}(a_2)$, ... dostaneme klesající
řetězec

\emph{\textbf{Lemma:} $N, LC$ implikuje $C$}

\textbf{Důkaz:} $\rightarrow \subseteq T \times T$, $b < a$ značí
$a \underbrace{\rightarrow ... \rightarrow}_{\text{alespoň 1}} b$

$\mathcal{P}(a)$ značí $\rightarrow$ je konfluentní v $a$

\includegraphics[height=50mm]{ilust/95.pdf}

\subsection{Příklad 9.1}

$\underline{xyxy}zyxyz \rightarrow xyzyxyz\\
x\underline{yxyzyxyz} \rightarrow \underline{xyxy}z \rightarrow xyz$

$ptsuq \rightarrow ptuq$

$c(s) \subseteq c(t) = c(u)\\
pvvq \rightarrow pvq$

\subsection{Prezentace pologrup}

$\underbrace{(a_1, ..., a_n)}_{\text{symboly}},
\underbrace{r_1 = s_1, ..., r_k = s_k}_{R\text{ (relace)}}\\
r_i, s_i \in \{a_1, ..., a_n\}^+$

Pro $(u, v) \in A^+ \times A^+$ na vstupu máme zjistit, zda $u = v$ vyplýva z
relací $(a, b, c, ba = bca, aba = cba)$\\
např.: $bac = bcac$\\
problém: vymyslete algoritmus, který by to řešil

\subsection{Věta}

Pro $k \geq 2$ obecně neřešitelné

Otevřený problém: pro $k = 1$

\subsection{Věta}

Pro prezentaci $(a_1, ..., a_n, u = v)$ kde (1) $|u| = |v|$, nebo (2)
$|u| > |v|$, $u$ se nepřekrývá (jeho prefix se sufixem), je problém řešitelný

\textbf{Důkaz:}

ad (1): $|p| > |q|$ pak $p \not\sim q$\\
pro $|p| = |q| = m$ vrcholy grafu budou všechna slova z $A^+$ délka $m$, hranou
spojím právě slova tvaru $ruv$, $rvs$. Hledáme cestu mezi $p$, $q$.

ad (2): $rus \rightarrow rvs \rightarrow rvtvw$\\
$rus \stackrel{s = tuw}{\rightarrow} rutvw \rightarrow rvtvw$\\
$u \rightarrow v$

\subsection{Důkaz lemmatu 6.1:}

$n = 1, \mathcal{V}$ třída všech grup\\
Pak volná je $(\mathbb{Z}, +)$, ta splňuje $xy = yx$, ale to neplatí ve všech
grupách

\textbf{Důkaz:}

$\mathcal{A} = (A, ...) \in \mathcal{O}\\
b_1, ..., b_n \in A\\
\alpha: M \rightarrow A, \alpha(a_i) = b_i, i = 1, ..., n$

\includegraphics[height=40mm]{ilust/96.pdf}\\
$\overline{\alpha}\iota = \alpha$

Na $p^{\mathcal{F}, n} (\iota(a_1), ...), q^{\mathcal{F}, n} (\iota(a_1), ...)$
aplikujeme $\overline{\alpha}$\\
$p^{\mathcal{F}, n} (\underbrace{\alpha(a_1)}_{b_1}, ...) = ...$

\subsection{Důkaz lemmatu 6.2}

\includegraphics[height=40mm]{ilust/97.pdf}

$\mathcal{V}' = Mod Id \mathcal{V}$ je uzavřené na $I, S, P$\\
nad $M$ tam existuje volná algebra

řekněme $\mathcal{F}'$\\
a vzhledem k $\iota'$

$M \stackrel{\iota'}{\rightarrow} F'\\
M \stackrel{\iota}{\rightarrow} F\\
F' \stackrel{\exists \text{ homomorfismus } \varphi}{\rightarrow} F\\
\iota = \varphi\iota'$

Ukážeme, že $\varphi$ je izomorfismus\\
$\varphi$ je surjektivní, neboť $\iota(M)$ generuje $\mathcal{F}$\\
prostota: nechť $u, v \in \mathcal{F}'\\
\exists p, q \in F_\mathcal{L} (u), a_1, ..., a_n \in M$ po 2 různé\\
$u = p^{\mathcal{F}', n} (\iota(a_1), ...)\\
v = q^{\mathcal{F}', n} (\iota(a_1), ...)$\\
nechť $\varphi(u) = \varphi(v)$, chceme $u = v$\\
$p^{\mathcal{F}', n} (\iota'(a_1), ...) = q ...$\\
Lemma dá $(p, q) \in Id \mathcal{V}$, tedy $\mathcal{F}' \models p = q$

\subsection{Důkaz věty 7.1:}

(2) $\Rightarrow$ (3)\\
$\mathcal{V}' = Mod Id \mathcal{V} \supseteq \mathcal{V}\\
\mathcal{A} \in \mathcal{V}', \mathcal{A} = (A, ...)$ s množinou generátorů
$M$\\
Pak $\mathcal{A} \in
H(\underbrace{\mathcal{F}_\mathcal{V}(M)}_{\text{volná ve } \mathcal{V}'})
\subseteq \mathcal{V}$\\
$\mathcal{A} \stackrel{?}{\in} \mathcal{V}$

? uspořádaná čtverice je uspořádaná dvojice uspořádaných dvojic ?\\
$(a, b, c, d) \qquad ((a, b), (c, d))$

Pro libovolnou třídu $\mathcal{V}$ je
$SH(\mathcal{V}) \subseteq HS(\mathcal{V})$\\
$\mathcal{A} \in \mathcal{V}$\\
$\alpha$ surjektivní homomorfismus\\
platí $\alpha^{-1}(\mathcal{C})$ je podalgebra, $\mathcal{C}$ je její
homomorfní obraz

\includegraphics[height=50mm]{ilust/98.pdf}

$x^2 = x\\
tps \leftrightarrow tpps\\
(s_j) \models x_{i_1} \cdot ... \cdot x_{i_k} =
x_{j_1} \cdot ... \cdot x_{j_k}$ n-ární\\
$\forall a_1, ..., a_n \in S, a_{i_1} ... a_{i_k} = a_{j_1} ... a_{j_l}$

\subsection{Unifikace}

$xauzau = yzbxaaby$, $a, b$ konstanty, $x, y, z, u$ slova\\
úkol: najít takové $x, y, z, u$ tak, aby se $LS = PS$.

(Vyřešil to Makanin - nalezl exponenciální algoritmus)

$x \rightarrow abb\\
y \rightarrow ab\\
z \rightarrow ba\\
u \rightarrow ?$

$abbaa(u)baaa(u)\\
abba|bab|baa|bab$

$u \rightarrow bab$

\includegraphics[height=40mm]{ilust/99.pdf}

za $x, y, z, u$ máme dosadit jisté termy aby se to rovnalo

\includegraphics[height=20mm]{ilust/100.pdf}

pravá strana

\includegraphics[height=60mm]{ilust/101.pdf}

\section{10. 5. 2011}

termíny: 2. 6. 14:00 D3, 15. 6. 15:00 D2, 29. 6. 14:00 D3

zápočet: např.: Pro která $n \in \mathbb{N}_0, d \in \mathbb{N}$ platí
$(T_3, \circ) \models x^n = x^{n + d}$

kdy $LC$ nedává $C$:

\includegraphics[height=50mm]{ilust/102.pdf}

Nechť $(S, \cdot)$ idempotentní pologrupa. Dokažde, že relace $\rho$ na $S$
definovaná vztahem $a \rho b :\Leftrightarrow aba = a, bab = b$ je kongruencí.

V jednom místě jsme potřebovali $a \rho b$ dá $ac \rho bc$, tj. $a = aba,
b = bab$ dá $acbcac = ac$, $(bcacbc = bc)$, $x^2 = x$

Varieta všech idempotentních pologrup je lokálně konečná (konečně generované
jsou konečné, resp. volná nad konečnou množinou je konečná)

\includegraphics[height=40mm]{ilust/103.pdf}

slova $u$: s $c(u) = \{a\} : a\\
c(u) = \{a, b\}: ab, ba, aba, bab$\\
slova s $c(u) = \{a, b, c\}: 3 + 3 \cdot 4 + 3 \cdot 4 + 3 \cdot 4$\\
s $c(u) \subseteq \{a, b, c\}$

\includegraphics[height=15mm]{ilust/104.pdf}

$L_{a_1 ... a_k} = A^* a_1 A^* a_2 A^* ... a_k A^*, k \geq 0 \qquad (*)\\
a_1, ..., a_k \in A\\
u = a_1 ... a_k$

$\mathcal{V}_{\frac{1}{2}}$: konečná sjednocení jazyků $(*)$,
$L_{ab} \cup L_{bc}$

\subsection{Věta}

$L \in \mathcal{V}_{\frac{1}{2}} \Leftrightarrow$ uspořádaný syntaktický monoid
jazyka $L$ splňuje $x \leq 1$\\
$u \sim_L v \Leftrightarrow \forall p, q \in A^*
(puq \in L \Leftrightarrow pvq \in L)\\
u \leq_L v \Leftrightarrow \forall p, q \in A^*
(puq \in L \Leftarrow pvq \in L)$

\includegraphics[height=40mm]{ilust/105.pdf}

\subsection{Simonova věta:}

$L \in \mathcal{V}_1 \Leftrightarrow$ syntaktický monoid jazyka $L$ je
$\mathcal{I}$-triviální.\\
$\mathcal{V}_1$: Booleovské kombinace jazyků tvary $(*)$\\
t.j.: $L_{u_{11}} \cap ... \cap L_{u_{1k_1}} \cap L'_{u_{1l_1}} \cap ... \cap
L'_{u_{1l_1}}\\
\cup ... \cup\\
L_{u_{m1}} \cap ... \cap L_{u_{mk_m}} \cap L'_{u_{ml_1}} \cap ... \cap
L'_{u_{ml_m}}$

$\mathcal{V}_{\frac{3}{2}}$: konečné sjednocení
$B_0^* a_1 B_1^* ... a_k B_k^*\\
a_1, ..., a_k \in A, B_0, ..., B_k \subseteq A \qquad (+)$

$U_2$: Booleova kombinace tvarů $(+)$

kánonický minimální úplný deterministický automat pro $L$\\
$u^{-1}L = \{v \in A^* | uv \in L\}\\
D_L = \{u^{-1}L | u \in A^*\}\\
\mathcal{D}_L = (D_L, A, \cdot, L, T)\\
u^{-1}L \cdot a = a^{-1}(u^{-1}L) (= (ua)^{-1}L)\\
u^{-1}L \in T \Leftrightarrow 1 \in u^{-1}L (\Leftrightarrow u \in L)$\\
(tak to chápou mistři)\\
(stavy jsou množiny slov, automat v podstatě přijímá sám sebe)

\textbf{Idea důkazu:}
$\mathcal{A}$ - automat, všechny stavy dostupné\\
$\mathcal{A} = (Q, A, \cdot, i, T)\\
\mathcal{L}(\mathcal{A}, q) = \{u \in A^* | q \cdot u \in T\}\\
p \sim q \Leftrightarrow \mathcal{L}(\mathcal{A}, p) =
\mathcal{L}(\mathcal{A}, q)$\\
$\sim$ je $Con\mathcal{A}, \mathcal{A}/\sim$ je minimální

$\mathcal{L}(\mathcal{D}_L, u^{-1}L) = \{v \in A^* | u^{-1}L \cdot v \in T\}\\
1 \in (uv)^{-1}L, u, v \in L, v \in u^{-1}L$

$B_L = \{u^{-1}Lv^{-1} | u, v \in A^*\}\\
\mathcal{B}_L = (B_L, A, \cdot, \circ, T)\\
q \cdot a = a^{-1}q\\
q \circ a = qa^{-1}\\
q \in T \Leftrightarrow 1 \in q$

\includegraphics[height=50mm]{ilust/106.pdf}\\
Level 1 pokud je graf acyklický

zkouška: jako minulé roky... prý

$a J b \Leftrightarrow \exists p, q, r, s: paq = b, rbs = a$
(viz programy JEPin, GAP)

(příklad na zápočet: Je třída všech svazů v jazyce binárních $\wedge, \vee$
uzavřená na operátor $\mathcal{H}$?)

\subsection{Konečná univerzální algebra}

Jazyk: binární $\cdot$, nulární $1$\\
$\mathcal{M}$ třída všech konečných monoidů\\
$(\Pi_M)_{M \in \mathcal{M}}$ je n-ární implicitní operace, je-li\\
$\forall M \rightarrow \mathcal{M}, \Pi_M : M^n \rightarrow M$\\
a $\forall M, N \in \mathcal{M}$, homomorfismus $\alpha: M \rightarrow N$

diagram
\includegraphics[height=30mm]{ilust/107.pdf}
je komutativní\\
$\alpha^n(a_1, ..., a_n) \mapsto (\alpha(a_1), ..., \alpha(a_n))$\\
t.j. $\forall a_1, ..., a_n \in M$

$t = x_{i_1} \cdot ... \cdot x_{i_m}, m \in \mathbb{N}_0, i_1, ..., i_m \in
\{1, ..., n\}$

$(x_{i_1} ... x_{i_m})_M (a_1, ..., a_n) = a_{i_1} ... a_{i_m}$ - násobení
v $M$

\includegraphics[height=40mm]{ilust/108.pdf}

$M \in \mathcal{M}, a \in M$ po 2 různé\\
$\overbrace{a ... a^2 ... a^3 ... \underset{= a^{m + d}}{a^m} ... a^{m + 1} ...
a^{m + d + 1}}^{}$

\emph{\textbf{Lemma:} Pro $a \in M \exists !$ idempotent v $<a>$}

$(a^k)^2 = a^k, k \geq m, d | k$\\
mezi $m, ..., m + d - 1$ je právě jedno takové $k$, označujeme $a^\omega$

$x^\omega$ je to unární implicitní operace\\
$\alpha: M \rightarrow N$ homomorfismus

\includegraphics[height=40mm]{ilust/109.pdf}

$(\alpha(a))^{2k} = \alpha(a^{2k}) = \alpha(a^k) = (\alpha(a))^k\\
(\alpha(a))^\omega = (\alpha(a))^k$

\emph{\textbf{Lemma:} Konečné monoidy splňující $x^\omega = 1$ jsou právě
konečné grupy}

\textbf{Pseudoidentita:} uspořádaná dvojice n-árních implicitních operací;
$M \models \Pi = \rho :\Leftrightarrow \Pi_M = \rho_M)$

\textbf{Důkaz:}\\
$(M, \cdot, 1)$ konečný monoid\\
$\Rightarrow$: $a \in M, \exists k \in \mathbb{N}: 1 = a^\omega = a^k\\
k = 1$ dá $a = 1$ - OK\\
$k \geq 2 : a^{k - 1}$ je inverze k $a$\\
$\Leftarrow$: v grupě je jediný idempotent a to je $1$. Pro $a \in M$ je
$a^\omega$ idempotent a proto $a^\omega = 1$.

\textbf{Pseudovarieta:} třída konečných monoidů uzavřených na $\mathcal{H}$,
$\mathcal{S}$, $\mathcal{P}_f$ (součiny konečných systémů)

Pro třídu $\mathcal{V}$ monoidů klademe $Fin\mathcal{V}$ je třída všech
konečných monoidů z $\mathcal{V}$.

\emph{\textbf{Lemma:} $\mathcal{V}$ varieta dá $Fin\mathcal{V}$ je
pseudovarieta.}

\textbf{Důkaz:} $M \in Fin\mathcal{V}, \alpha: M \rightarrow N
(\in Fin M))$ homomorfismus. $N \in H(\mathcal{V}) \subseteq \mathcal{V}$

\emph{\textbf{Lemma:} Třídy konečných monoidů zadané pseudoidentitami jsou
pseudovariety}

\textbf{Důkaz:}\\
$M, N \in \mathcal{M}, \alpha: M \rightarrow N$ surjektivní homomorfismus,
$M \models \Pi = \rho$ n-ární, chci $N \models \Pi = \rho$

\includegraphics[height=30mm]{ilust/110.pdf}

$\exists a_1, ..., a_n \in M$ tak, že $\alpha(a_1) = b_1, ...$

$\Pi_M (b_1, ..., b_n) = \Pi_N (\alpha(a_1), ..., \alpha(a_n)) =
\alpha(\Pi_M(a_1, ..., a_n)) = \alpha(\rho_M(a_1, ..., a_n)) =
\rho_M(b_1, ..., b_n)$\\
$\mathcal{S}$, $\mathcal{P}_f$ podobně

\subsection{Věta: (Reiterman)}

Pseudovariety jdou zadat pseudoidentitami

uzavřenost na $\mathcal{H}$, $\mathcal{S}$, $\mathcal{P}
\underset{\underset{\text{těžké}}{\rightarrow}}
{\overset{\text{lehké}}{\leftarrow}}$
zadatelnost identitami

\subsection{Věta (Eilenberg, Baldwin, ...)}

Pseudovariety jsou právě třídy $Fin\mathcal{V}$, kde $\mathcal{V}$ je
sjednocení neklesající posloupnosti variet

\includegraphics[height=40mm]{ilust/111.pdf}

Pro grupy: $\mathcal{V}_n =$ grupy splňující $x^{n!} = 1$

\textbf{Důkaz:}

uzavřenost na $\mathcal{H}$, $M \in Fin\mathcal{V}, \alpha: M \rightarrow N$
surjektivní homomorfismus. $\exists k: M \in \mathcal{V}_k$, pak i
$N \in \mathcal{V}_k$

$M_1 \times ... \times M_n\\
\mathcal{V}_{i_1} ... \mathcal{V}_{i_n}$

\section{17. 05. 2011}

\subsection{Prezentace pologrupy}

$(\underbrace{a, b, c;}_{\text{množina generátorů }M}
\underbrace{x^2 = x}_{\text{množina indentit }\Pi},
\underbrace{aba = a, bab = b}_{\text{množina relací }P})$

$acbcac \stackrel{?}{=} ac$

\includegraphics[height=40mm]{ilust/112.pdf}\\
volná idempotentní nad $\{a, b, c\}$

existence: vezmu $M^+$, podělím ji úplně invariantní kongruencí generovanou
$\Pi$ (tím dostanu volnou v $Mod\Pi$ nad $M$). Tyto podělím kongruencí
generovanou $P$.

$\rho$ je úplně invariantní kongruencí, je-li to kongruence a\\
$\forall \alpha \in \underbrace{End\mathcal{A}}_{\text{homomorfismus do sebe}},
a \rho b$ dá $\alpha(a) \rho \alpha(b)$

\subsection{Věta (Eidenberg, Baldwin, ...)}

\includegraphics[height=40mm]{ilust/111.pdf}

$\underbrace{\mathcal{V}_1 \subseteq \mathcal{V}_2 \subseteq ...
\text{ variety; }\mathcal{V} =
\underset{n \in \mathbb{N}}{\bigcup}\mathcal{V}_n}_{(*)}$

$\forall$ pseudovariety $\mathcal{W}$ $\exists (*)$ tak, že $W = Fin V$\\
podgrupy $\mathcal{V}_n = Mod (x^{n'} = 1)$

\subsection{Věta}

$(S, \cdot)$ je konečná podgrupa (speciální monoid) (název: aperiodické
pologrupy)\\
$(*)$ je ekvivalentní:

\begin{enumerate}[(i)]
\item
$(S, \cdot)$ má jen triviální podgrupy
\item
$\forall a \in S \exists k \in \mathbb{N}: a^{k + 1} = a^k$
\item
$(S, \cdot) \models x^{\omega + 1} = x^\omega$
(t.j. $\forall a \in S: a^{\omega + 1} = a^\omega$)
\end{enumerate}

\textbf{Důkaz:} Pro $a \in S: a ... a^2 ... a^3 ... \underset{= a^d}{a^k} ...
a^{k + 1} ... a^{k + d - 1}$ po 2 různé. $a^\omega = a^l$ je podgrupa s
netriviálním prvkem $a^\omega$.

$(i) \Rightarrow (ii)$ případně $\exists a \in S: \forall k \in \mathbb{N}:
a^{k + 1} \neq a^k$, pak $d \geq 2$ a máme netriviální podgrupy\\
$(ii) \Rightarrow (iii)$ máme $\forall a \in S: d = 1$\\
$(iii) \Rightarrow (i)$\\
\includegraphics[height=30mm]{ilust/113.pdf}\\
$e^2 = e, a \neq e$\\
$\exists k: \underbrace{a^k}_{= a^\omega} = e, k \geq 2$\\
$a^{\omega + 1} = ea = a, a^\omega = e$ spor

Baldwin: $\overset{???}{\text{přísl.}}$ $\mathcal{V}_n = Mod(x^{n + 1} = x^n)$

$M$ konečný monoid je $\mathcal{J}$-triviální: $\forall a, b, p, q, r, s \in M:
paq = b, rbs = a$ dá $a = b$

\subsection{Věta}

Konečný monoid $M$ je $\mathcal{J}$-triviální $\Leftrightarrow$ splňuje
$x^{\omega + 1} = x^\omega, (xy)^\omega = (yx)^\omega$\\
$(\forall a, b \in S: (ab)^\omega = (ba)^\omega)$

\textbf{Důkaz:}\\
$\Rightarrow:$ $1 \cdot a^\omega \cdot a = a^{\omega + 1}\\
1 \cdot a^{\omega + 1} \cdot a^{d - 1} = a^\omega\\
\mathcal{J}$-triviální dá $a^{\omega + 1} = a^\omega$

$(ab)^\omega = (ab)^k = (ab)^{2k} = ...\\
(ba)^\omega = (ba)^l = (ba)^{2l} = ...\\
(ba)^\omega = (ba)''' b \underbrace{(ab)^\omega}_{(ab)^k} a (ba)'''$

$(ab)^\omega = (ab) a (ba)^\omega b (ab)$\\
tedy $(ab)^\omega \mathcal{J} (ba)^\omega$ t.j. $(ab)^\omega (ba)^\omega$

\emph{\textbf{Lemma:}}
\begin{enumerate}[(i)]
\item
$M, N$ $\mathcal{J}$-triviální dá $M \times N$ $\mathcal{J}$-triviální
\item
$M$ $\mathcal{J}$-triviální, $N \subseteq M$ dá $N$ $\mathcal{J}$-triviální
\item
surjektivní homomorfismus
\end{enumerate}

\textbf{Důkaz:} plyne z předchozího

\subsection{Varieta jazyků}

Pro libovolné konečné $A$ je dána množina $\mathcal{L}(A)$ regulárních jazyků
nad $A$ splňující:
\begin{enumerate}[(i)]
\item
$\forall A$ je $\mathcal{L}(A)$ uzavřená na binární $\cap, \cup$ a $'$ a
derivace\\
$p^{-1}Lq^{-1} = \{u \in A^* | puq \in L\}$ derivace jazyka $L$
\item
$f: B^* \rightarrow A^*$ homomorfismus, $K \in \mathcal{L}(A)$ dá
$f'(K) \in \mathcal{L}(B)$
\end{enumerate}

Levely:\\
$2\\
\frac{3}{2}:$ konečná sjednocení $B_0^* a_1 B_1^* ... a_k B_k^*\\
1\\
\frac{1}{2}:$ konečná sjednocení $A^* a_1 A^* a_2 ... a_k A^*$

Pozitivní varieta: nechce se uzavřít na komplement

\subsection{Věta (Eilenberg)}

Variety jazyků $\leftrightarrow$ pseudovariety monoidů\\
$\mathcal{L} \mapsto
\underbrace{<\{\underbrace{M(L)}_{\text{syntaktický monoid}} | L \in
\mathcal{L}(A), A\text{ konečné}\}>}_{\text{generování pseudovariety}}$

$\mathcal{V} \mapsto \mathcal{L}(A) = \{L \in A^* | M(L) \in \mathcal{V}\}$

\textbf{Příklad:}\\
level 1 $\leftrightarrow$ $\mathcal{J}$-triviální\\
star-free $\leftrightarrow$ aperiodické monoidy

star-free: jdou zapsat zobecněným regulárním výrazem $*$; například
$(ab)^* ad \{a, b\}$\\
zobecněné povolují i $\cap, '$.

\subsection{Unifikace}

$x^5 y^7 = c^8 d^2 e^3\\
\downarrow \sigma: x \mapsto c^{-4} d^{-1} e^{-5} z^{-7};
y \mapsto c^4 d e^4 z^5\\
\downarrow \iota: z \mapsto c^2 d \qquad z \mapsto t^2$

\subsubsection{Lineární geofantické rovnice}

$(*) a_1 x_1 + ... + a_n x_n = b; a_1, ..., a_n, b \in \mathbb{Z}$\\
hledáme (všechny) řešení v $\mathbb{Z}$\\
$d = nsd(a_1, ..., a_n)$\\
nalevo jsou právě násobky $d$.\\
$(*)$ řešitelná $\Leftrightarrow d | b$

lze předpokládat $d = 1$\\
$n = 1: x = b$ umíme řešit

indukční krok:\\
$d = nsd(a_1, ..., a_{n - 1})\\
(*)$ uvážíme $mod \; d: a_1 x_1 + ... + a_n x_n \equiv b (mod \; d)$

t.j.: $a_n x_n \equiv b (mod \; d) \qquad (+)\\
nsd(a_n, d) = 1$\\
máme řešení $x_n \equiv c (mod \; d)$\\
t.j.: $x_n = c + d t$, kde $t \in \mathbb{Z}$\\
dosadíme do $(*):\\
a_1 x_1 + ... + a_{n - 1} x_{n - 1} = b - a_n (c + dt) /:d\\
d | a_1, ..., d | a_{n - 1}\\
d | b - a_n c$ z $(+)$ a $(\ddagger)$

$a_1' x_1 + ... + a_{n - 1}' x_{n - 1} = b'\\
nsd(a_1', ..., a_{n - 1}') = 1$

$(*) 18x + 20y + 15z = 1 \qquad nsd(18, 20, 15) = 1\\
d = nsd(18, 20) = 2\\
15z \equiv 1 (mod \; 2)\\
z \equiv 1 (mod \; 2)\\
z = 1 + 2s, s \in \mathbb{Z}$

dosadíme do $(*)$:\\
$18x + 20y = 1 - 15(1 + 2s)\\
18x + 20y = -14 - 30s /:2\\
9x + 10y = -7 - 15s\\
d = 9 \qquad 10y \equiv 7 - 15s (mod \; 9)$\\
neboli $y = 2 + 3s + 9t, t \in \mathbb{Z}\\
9x = -7 - 15s - 10(2 + 3s + 9t)$\\
t.j.: $9x = -27 - 45s - 90t /:9\\
x = -3 - 5s - 10t$

\subsection{Unifikace v komutativních grupách s konstantami}

$x^5 y^7 = c^8 d^2 e^3$\\
kvůli $c$: $5\xi + 7\eta = 8\\
x \mapsto c^\xi...\\
y \mapsto c^\eta...\\
\eta = 4 + 5t\\
\xi = -4 - 7t$

kvůli $d$: $5\xi + 7\eta = 2\\
x \mapsto ...d^\xi...\\
y \mapsto ...d^\eta...\\
\eta = 1 + 5t\\
\xi = -1 - 7t$

kvůli $e$: $5\xi + 7\eta = 3\\
x \mapsto ...e^\xi...\\
y \mapsto ...e^\eta...\\
\eta = 4 + 5t\\
\xi = -5 - 7t$

nejobecnější řešení:\\
$x \mapsto c^{-4} d^{-1} e^{-5} z^{-7}\\
y \mapsto c^4 d e^4 e^5$

\subsection{Komutativní monoidy (pro informatiky $AC1$)}

$\underbrace{A}_{\text{asociativita}}\overbrace{C}^{\text{komutativita}}
\underbrace{1}_{\text{neutrální prvek}}$

elementární problém = bez konstant\\
$x^6y^{10} = z^7$

nejobecnější řešení:\\
$x \rightarrow z_1^3 z_2^2 z_3^7 z_4 z_5^0\\
y \rightarrow z_1 z_2^3 z_3^6 z_4^5 z_5^7\\
z \rightarrow z_1^4 z_2^6 z_3^6 z_4^8 z_5^{10}$

vede na rovnici $6\xi + 10\eta = 7\zeta \qquad (*)\\
x \rightarrow t^\xi\\
y \rightarrow t^\eta\\
z \rightarrow t^\zeta$

Musíme popsat všechna minimální nezáporná řešení $(*)$.\\
minimální = není součtem 2 jiných

\subsection{Věta}

Lineární diofantická rovnice má konečné množství minimálních nezáporných
řešení

Všechny minimální nezáporné: $(3, 1, 4), (2, 3, 6), (7, 0, 6), (1, 5, 8),
(0, 7, 10)$

obvyklým způsobem řešíme $b\xi + 10\eta - 7\zeta = 0$

$
\left( {\begin{array}{c}
x\\
y\\
z
\end{array} } \right)
=
\left( {\begin{array}{cc}
-1 & -5\\
2 & 3\\
2 & 0
\end{array} } \right)
\left( {\begin{array}{c}
\alpha\\
\beta
\end{array} } \right)
\qquad \alpha, \beta \in \mathbb{Z}
$

\end{document}

